On the Complexity of Scheduling Peter Brucker University of Osnabrueck Germany 1.Scheduling Problems In a scheduling problem one has to find time slots in which activities (or jobs) should be processed under given constraints. The main constraints are resource constraints and precedence constraints between activities. A quite general scheduling problem is the Resource Constrained Project Scheduling Problem (RCPSP) which can be formulated as follows: The RCPSP We have вЂў Activities j = 1, ... , n with processing times pj. вЂў Resources k = 1, ... , r. A constant amount of Rk units of resource k is available at any time. During processing, activity j occupies rjk units of resource k for k = 1, ... , r. вЂў Precedence constrains i п‚® j between some activities i, j with the meaning that activity j cannot start before i is finished.. The RCPSP The objective is to determine starting times Sj for all activities j in such a way that вЂў at each time t the total demand for resource k is not greater than the availability Rk for k = 1, ... , r, вЂў the given precedence constraints are fulfilled, i. e. Si+ pi п‚Ј Sj if i п‚® j , The RCPSP вЂў some objective function f( C1, ... , Cn) is minimized where Cj = Sj + pj is the completion time of activity j. The fact that activities j start at time Sj and finish at time Sj + pj implies that the activities j are not preempted. We may relax this condition by allowing preemption (activity splitting). The RCPSP If preemption is not allowed the vector S = (Sj) defines a schedule. S is called feasible if all resource and precedence constraints are fulfilled. One has to find a feasible schedule which minimizes the objective function f( C1, ... , Cn). In project planning f( C1, ... , Cn) is often replaced by the makespan Cmax which is the maximum of all Cj - values. An Example Consider a project with n = 4 activities, r = 2 resources with capacities R1 = 5 and R2 = 7, a precedence relation 2 п‚® 3 and the following data: An Example 2п‚®3 A corresponding schedule with minimal makespan The RCPSP вЂў The constraints Si + pi п‚Ј Sj may be replaced by Si + dij п‚Ј Sj (positive and negative timelags). вЂў With time-lags we may model release times rj or deadlines dj . вЂў We may have more than one objective function (multi-criteria optimization). вЂў There are other generalizations. RCPSP with Multiple Modes вЂў Associated with each activity j is a set Mj of modes (processing alternatives). вЂў The processing time pjm and per period usage rjkm of resource k for activity j depends on mode m. вЂў One has to assign a mode to each activity and to schedule the activities in the assigned modes. Applications вЂў Production scheduling вЂў Robotic cell scheduling вЂў Computer processor scheduling вЂў Timetabling вЂў Personnel scheduling вЂў Railway scheduling вЂў Air traffic control вЂў etc. Assumptions вЂў All data are assumed to be integers. вЂў We consider only off-line scheduling problems (on-line scheduling problems will be discussed in another talk). Next machine scheduling problems will be discussed in detail. 2. Machine Scheduling Problems and their Classification вЂў Most machine scheduling problems are special cases of the RCPSP. Here we will consider вЂў single machine problems, вЂў parallel machine problems, and вЂў shop scheduling problems. Single machine problems вЂў We have n jobs j =1, ... , n to be processed on a single machine. Additionally precedence constraints between the jobs may be given. вЂў This problem can be modeled by an RCPSP with r = 1, R1 = 1, and rj1 = 1 for all jobs j. Parallel Machine Problems вЂў We have jobs j as before and m identical machines M1, ... , Mm . The processing time for j is the same on each machine. One has to assign the jobs to the machines and to schedule them on the assigned machines. вЂў This problem corresponds to an RCPSP with r = 1, R1 = m, and rj1 = 1 for all jobs j. Parallel Machine Problems Parallel Machine Problems вЂў For unrelated machines the processing time pjk depends on the machine Mk on which j is processed. вЂў The machines are called uniform if pjk = pj/rk. вЂў In a problem with multi-purpose machines a set of machines mj is is associated with each job j indicating that j can be processed on one machine in mj only. Shop Scheduling Problems вЂў In a general shop scheduling problem we have m machines M1, ... , Mm and n jobs j = 1, ... , n. вЂў Job j consists of n(j) operations O1j, O2j, ... , On(j)j where Oij must be processed for pij time units on a dedicated machine mij пѓЋ {M1, ... , Mm }. вЂў Two operations of the same job cannot be processed at the same time. Precedence constraints are given between the operations. Shop Scheduling Problems To model the general shop scheduling problem as RCPSP we consider вЂў r = n + m resources k = 1, ..., n + m with Rk = 1 for all k. While resources k = 1, ... , m correspond to the machines, resources m + j (j = 1, ... , n) are needed to model that different operations of the same job cannot be scheduled at the same time. вЂў n(1) + n(2) + ... + n(n) activities Oij where operation Oij needs one unit of вЂњmachine resourceвЂќ mij and one unit of the вЂњjob resourceвЂќ m + j. Shop Scheduling Problems вЂў A job-shop problem is a general shop scheduling problem with chain precedence constraints of the form O1j п‚® O2j п‚® ... п‚® On(j)j. вЂў A flow-shop problem is a special job-shop problem with n(j) = m operations for j = 1, ..., n and mij = Mi for i = 1, ..., m and j = 1, ..., n . Shop Scheduling Problems вЂў In a permutation flow-shop problem the jobs have to be processed in the same order on all machines. Shop Scheduling Problems вЂў An open-shop problem is like a flow-shop problem but without precedence constraints between the operations. Classification of Scheduling Problems Classes of scheduling problems can be specified in terms of the three-field classification a | b | g where п‚• a specifies the machine environment, п‚• b specifies the job characteristics, and п‚• g describes the objective function(s). Machine Environment To describe the machine environment the following symbols are used: вЂў 1 single machine вЂў P parallel identical machines вЂў Q uniform machines вЂў R unrelated machines вЂў MPM multipurpose machines вЂў J job-shop вЂў F flow-shop вЂў O open-shop The above symbols are used if the number of machines is part of the input. If the number of machines is fixed to m we write Pm, Qm, Rm, MPMm, Jm, Fm, Om. Job Characteristics вЂў вЂў вЂў вЂў pmtn preemption rj release times dj deadlines pj = 1 or pj = p or pj пѓЋ {1,2} restricted processing times вЂў prec arbitrary precedence constraints вЂў intree (outtree) intree (or outtree) precedences вЂў chains chain precedences вЂў series-parallel a seriesparallel precedence graph Objective Functions Two types of objective functions are most common: вЂў bottleneck objective functions max {fj(Cj) | j= 1, ... , n}, and вЂў sum objective functions S fj(Cj) = f1(C1) + f2(C2) + ... ... + fn(Cn) . Objective Functions Cmax and Lmax symbolize the bottleneck objective functions with fj(Cj) = Cj (makespan) and fj(Cj) = Cj - dj (maximum lateness), respectively. Common sum objective functions are: п‚• S Cj (mean flow-time) and S wj Cj (weighted flow-time) Objective Functions п‚• S Uj (number of late jobs) and S wj Uj (weighted number of late jobs) where Uj = 1 if Cj > dj and Uj = 0 otherwise. п‚• S Tj (sum of tardiness) and S wj Tj (weighted sum of tardiness) where the tardiness of job j is given by Tj = max { 0, Cj - dj }. Examples вЂў вЂў вЂў вЂў вЂў вЂў вЂў 1 | prec; pj = 1 | S wj Cj P2 | | Cmax P | pj = 1; rj | S wj Uj R2 | chains; pmtn | Cmax J3 | n = 3 | Cmax F | pij = 1; outtree; rj | S Cj Om | | pj = 1 | S Tj 3. Complexity Theory 3.1 Polynomial algorithms 3.2 Classes P and NP 3.3 NP- complete and NP- hard problems 3.1 Polynomial algorithms вЂў An algorithm h transforms an input x into an output h(x). h(x) is the answer for a corresponding problem solved by the algorithm. вЂў |x| denotes the length of input x with respect to some binary encoding. вЂў An algorithm is called polynomial if h(x) can be computed in at most O(p(|x| ) step where p is a polynomial. 3.1 Polynomial algorithms вЂў A problem is called polynomially solvable if it can be solved by a polynomial algorithm. Example 1 | | S wjCj can be solved by scheduling the jobs in an ordering of non-increasing wj/pj - values. Complexity: O(n log n) 3.1 Polynomial algorithms вЂў If we replace the binary encoding by an unary encoding we get the concept of a pseudo-polynomial algorithm. Example An algorithm for a scheduling problem with computational effort O(S pj) is pseudopolynomial. 3.2 Classes P and NP вЂў A problem is called a decision problem if the output range is {yes, no}. вЂў We may associate with each scheduling problem a decision problem by defining a threshold k for the objective function f. The decision problem is: Does a feasible schedule S exist satisfying f(S) п‚Ј k? вЂў P is the class of decision problems which are polynomially solvable. 3.2 Classes P and NP вЂў NP is the class of decision problems with the property that for each вЂњyesвЂќ-answer a certificate exists which can be used to verify the вЂњyesвЂќ-answer in polynomial time. вЂў Decision versions of scheduling problems belong to NP (a вЂњyesвЂќ-answer is certified by a feasible schedule S with f(S) п‚Ј k). вЂў P пѓЌ NP holds. It is open whether P = NP. 3.3 NP- complete and NP- hard problems вЂў For two decision problems P and Q, we say that P reduces to Q (denoted by P a Q) if there exists a polynomial-time computable function g that transforms inputs for P into inputs for Q such that x is a вЂњyesвЂќ-input for P if and only if g(x) is a вЂњyesвЂќ-input for Q. 3.3 NP- complete and NP- hard problems Properties of polynomial reductions: вЂў Let P, Q be decision problems. If P a Q then Q пѓЋ P implies P пѓЋ P (and, equivalently, P пѓЏ P implies Q пѓЏ P) . вЂў Let P, Q, R be decision problems. If P a Q and Q a R, then P a R. 3.3 NP- complete and NP- hard problems вЂў A decision problem Q is called NP - complete if Q пѓЋ NP and, for all other decision problems P пѓЋ NP, we have P a Q. If any single NP- complete decision problem Q could be solved in polynomial time then we would have P = NP. 3.3 NP- complete and NP- hard problems To prove that a decision problem P is NP complete it is sufficient to prove the following two properties: вЂў P пѓЋ NP, and вЂў there exist an NP- complete problem Q with Q a P. 3.3 NP- complete and NP- hard problems An optimization problem is NP- hard if its decision version is NP- complete. 3.3 NP- complete and NP- hard problems Cook [1971] has shown that the satisfiability problem from Boolean logic is NP- complete. Using this result he used reduction to prove that other combinatorial problems are NPcomplete as well. In a follow-up paper Karp [1972] derived NPcompleteness results for many other problems. 4. Complexity of machine scheduling problems Complexity results for different classes of scheduling problems can be found under http://www.mathematik.uniosnabrueck.de/research/OR/class/ These results are based on вЂў results found in the literature, and вЂў elementary reductions between scheduling problems. 4. Complexity of machine scheduling problems In these web-pages for several classes of machine scheduling problems the following results are listed: вЂў the hardest problems which are known to be polynomially solvable, вЂў the easiest problems which are known to be NP hard, вЂў the hardest and easiest problems which are open. Elementary reductions Hereby the following elementary reductions are used Elementary reductions Elementary reductions Elementary reductions For single machine problems we have more specific elementary reductions. Polynomially solvable single machine problems NP - hard single machine scheduling problems Minimal and maximal open problems Polynomially solvable parallel machine problems without preemption Polynomially solvable parallel machine problems without preemption Polynomially solvable parallel machine problems without preemption NP- hard parallel machine problems without preemption NP- hard parallel machine problems without preemption Minimal and maximal open problems 5. How to Live with NP - hard Scheduling Problems? Small sized problems can be solved by вЂў Mixed integer linear programming вЂў Dynamic programming вЂў Branch and bound methods To solve problems of larger size one has to apply вЂў Approximation algorithms вЂў Heuristics 6. Other Types of Scheduling Problems There are other classes of scheduling problems. Some of them are discussed in this book. вЂў Due-date scheduling вЂў Batching problems вЂў Multiprocessor task scheduling вЂў Cyclic scheduling вЂў Scheduling with controllable data вЂў вЂў вЂў вЂў вЂў Shop problems with buffers Inverse scheduling No-idle time scheduling Multi-criteria scheduling Scheduling with noavailable constraints 6. Other Types of Scheduling Problems Scheduling problems are also discussed in connection with other areas: вЂў Scheduling and transportation вЂў Scheduling and game theory вЂў Scheduling and location problems вЂў Scheduling and supply chains References P. Brucker (2007), Scheduling Algorithms, fifth edition, Springer, Heidelberg M.R. Garey, D.S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco. http://www.mathematik.uniosnabrueck.de/research/OR/class/

1/--страниц