251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

being subject to deadlines (this prob- lem is strongly NP-hard). Chen and Bul\ufb01n (1993) present a detailed overview of the state of the art in multi-objective single machine scheduling. The book by T\u2019kindt and Billaut (2002, 2006) is entirely focused on multi-objective schedul- ing. The material in Section 4.4 dealing with the Travelling Salesman Problem is entirely based on the famous paper by Gilmore and Gomory (1964). For more results on scheduling with sequence dependent setup times see Bianco, Ricciardelli, Rinaldi and Sassano (1988), Tang (1990) and Wittrock (1990). Scheduling with the jobs belonging to a given (\ufb01xed) number of families has received a fair amount of attention in the literature. At times, these types of models have also been referred to as batch scheduling models (since the consecutive processing of a set of jobs from the same family may be regarded as a batch). Monma and Potts (1989) discuss the complexity of these scheduling problems. An excellent overview of the literature on this topic is presented in the paper by Potts and Kovalyov (2000). Brucker (2004) in his book also considers this class of models and refers to it as s-batching (batching with jobs processed in series). When the machine is capable of processing multiple jobs in parallel, the machine is often referred to as a batching machine. An important paper con- cerning batch processing and batching machines is the one by Brucker, Gladky, Hoogeveen, Kovalyov, Potts, Tautenhahn, and van de Velde (1998). Potts and Kovalyov (2000) provides for this class of models also an excellent survey. Brucker (2004) considers this class of models as well and refers to them as p-batching (batching with jobs processed in parallel). Chapter 5 Parallel Machine Models (Deterministic) 5.1 The Makespan without Preemptions . . . . . . . . . . . . . . . 112 5.2 The Makespan with Preemptions . . . . . . . . . . . . . . . . . . 122 5.3 The Total Completion Time without Preemptions . . . 130 5.4 The Total Completion Time with Preemptions . . . . . . 134 5.5 Due Date Related Objectives . . . . . . . . . . . . . . . . . . . . . 136 5.6 Online Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 5.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 A bank of machines in parallel is a setting that is important from both a the- oretical and a practical point of view. From a theoretical point of view it is a generalization of the single machine, and a special case of the \ufb02exible \ufb02ow shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Also, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems. In this chapter several objectives are considered. The three principal objec- tives are the minimization of the makespan, the total completion time, and the maximum lateness. With a single machine the makespan objective is usually only of interest when there are sequence dependent setup times; otherwise the makespan is equal to the sum of the processing times and is independent of the sequence. When dealing with machines in parallel the makespan becomes an objective of considerable interest. In practice, one often has to deal with the problem of balancing the load on machines in parallel; by minimizing the makespan the scheduler ensures a good balance. One may actually consider the scheduling of parallel machines as a two step process. First, one has to determine which jobs have to be allocated to which machines; second, one has to determine the sequence of the jobs allocated to each machine. With the makespan objective only the allocation process is im- portant. 111M.L. Pinedo, Scheduling, DOI: 10.1007/978-0-387-78935-4 c© Springer Science+Business Media, LLC 2008 5, 112 5 Parallel Machine Models (Deterministic) With parallel machines, preemptions play a more important role than with a single machine. With a single machine preemptions usually only play a role when jobs are released at di\ufb00erent points in time. In contrast, with machines in parallel, preemptions are important even when all jobs are released at the same time. For most models considered in this chapter there are optimal schedules that are non-delay. However, if there are unrelated machines in parallel and the total completion time must be minimized without preemptions, then the optimal schedule may not be non-delay. Most models considered in this chapter fall in the category of the so-called o\ufb04ine scheduling problems. In an o\ufb04ine scheduling problem all data (e.g., pro- cessing times, release dates, due dates) are known in advance and can be taken into account in the optimization process. In contrast, in an online scheduling problem, the problem data are not known a priori. The processing time of a job only becomes known the moment it is completed and a release date only becomes known the moment a job is released. Clearly, the algorithms for online scheduling problems tend to be quite di\ufb00erent from the algorithms for o\ufb04ine scheduling problems. The last section in this chapter focuses on online schedul- ing of parallel machines. The processing characteristics and constraints considered in this chapter in- clude precedence constraints as well as the set functions Mj . Throughout this chapter it is assumed that p1 \u2265 · · · \u2265 pn. 5.1 The Makespan without Preemptions First, the problem Pm || Cmax is considered. This problem is of interest because minimizing the makespan has the e\ufb00ect of balancing the load over the various machines, which is an important objective in practice. It is easy to see that P2 || Cmax is NP-hard in the ordinary sense as it is equivalent to PARTITION (see Appendix D). During the last couple of decades many heuristics have been developed for Pm || Cmax. One such heuristic is described below. The Longest Processing Time \ufb01rst (LPT) rule assigns at t = 0 the m longest jobs to the m machines. After that, whenever a machine is freed the longest job among those not yet processed is put on the machine. This heuristic tries to place the shorter jobs more towards the end of the schedule, where they can be used for balancing the loads. In the next theorem an upper bound is presented for Cmax(LPT ) Cmax(OPT ) , where Cmax(LPT ) denotes the makespan of the LPT schedule and Cmax(OPT ) denotes the makespan of the (possibly unknown) optimal schedule. This type 5.1 The Makespan without Preemptions 113 of worst case analysis is of interest as it gives an indication of how well the heuristic is guaranteed to perform as well as the type of instances for which the heuristic performs badly. Theorem 5.1.1. For Pm || Cmax Cmax(LPT ) Cmax(OPT ) \u2264 4 3 \u2212 1 3m . Proof. By contradiction. Assume that there exists one or more counterexamples with the ratio strictly larger than 4/3\u22121/3m. If more than one such counterex- ample exist, there must exist an example with the smallest number of jobs. Consider this \u201csmallest\u201d counterexample and assume it has n jobs. This smallest counterexample has a useful property: under LPT the shortest job is the last job to start its processing and also the last job to \ufb01nish its process- ing. That this is true can be seen as follows: \ufb01rst, under LPT by de\ufb01nition the shortest job is the last to start its processing. Also, if this job is not the last to complete its processing, the deletion of this smallest job will result in a counterexample with fewer jobs (the Cmax(LPT ) remains the same while the Cmax(OPT ) may remain the same or may decrease). So for the smallest coun- terexample the starting time of the shortest job under LPT is Cmax(LPT )\u2212pn. Since at this point in time all other machines are still busy it follows that Cmax(LPT )\u2212 pn \u2264 \u2211n\u22121 j=1 pj m . The right hand side is an upper bound on the starting time of the shortest job. This upper bound is achieved when scheduling the \ufb01rst n\u2212 1 jobs according to LPT results in each machine having exactly