COMPLEX SCHEDULING

By J. FITAS

CONTENTS SCHEDULING MODELS THE RCPSP AND SOME GENERALIZATIONS THE RCPSP APPLICATIONS OF THE RCPSP MACHINE SCHEDULING SINGLE-MACHINE SCHEDULING PARALLEL MACHINE SCHEDULING SHOP SCHEDULING MULTI-PROCESSOR TASK SCHEDULING REFERENCE NOTES ALGORITHMS AND COMPLEXITY EASY AND HARD PROBLEMS POLYNOMIALLY SOLVABLE PROBLEMS NP-HARD PROBLEMS SHORTEST PATH ALGORITHMS DIJKSTRA’S ALGORITHM LABEL-CORRECTING ALGORITHMS DETECTION OF NEGATIVE CYCLES FLOYD-WARSHALL ALGORITHM LINEAR AND INTEGER PROGRAMMING LINEAR PROGRAMS AND THE SIMPLEX ALGORITHM DUALITY THE REVISED SIMPLEX METHOD LINEAR PROGRAMS WITH INTEGER VARIABLES DELAYED COLUMN GENERATION TECHNIQUES NETWORK FLOW ALGORITHMS THE MINIMUM COST ?OW PROBLEM THE RESIDUAL NETWORK AND DECOMPOSITION OF ?OWS THE MAXIMUM ?OW PROBLEM FLOWS AND CUTS ALGORITHMS FOR THE MAXIMUM ?OW PROBLEM ALGORITHMS FOR THE MINIMUM COST ?OW PROBLEM BRANCH-AND-BOUND ALGORITHMS BASIC CONCEPTS THE KNAPSACK PROBLEM DYNAMIC PROGRAMMING LOCAL SEARCH AND GENETIC ALGORITHMS LOCAL SEARCH ALGORITHMS GENETIC ALGORITHMS RESOURCE-CONSTRAINED PROJECT SCHEDULING BASICS CONSTRAINT PROPAGATION BASIC RELATIONS START-START DISTANCE MATRIX SYMMETRIC TRIPLES AND EXTENSIONS DISJUNCTIVE SETS CUMULATIVE RESOURCES CONSTRAINT PROPAGATION FOR THE MULTI-MODE CASE REFERENCE NOTES LOWER BOUNDS COMBINATORIAL CONSTRUCTIVE LOWER BOUNDS AN LP-BASED CONSTRUCTIVE LOWER BOUND AN LP-BASED DESTRUCTIVE METHOD A DESTRUCTIVE METHOD FOR THE MULTI-MODE CASE HEURISTIC METHODS A CLASSI?CATION OF SCHEDULES SCHEDULE GENERATION SCHEMES PRIORITY-BASED HEURISTICS HEURISTICS FOR THE MULTI-MODE CASE AN ALGORITHM BASED ON PRECEDENCE TREES AN ALGORITHM BASED ON EXTENSION ALTERNATIVES AN ALGORITHM BASED ON DELAYING ALTERNATIVES AN ALGORITHM BASED ON SCHEDULE SCHEMES ALGORITHMS FOR THE MULTI-MODE CASE GENERAL OBJECTIVE FUNCTIONS REGULAR FUNCTIONS LINEAR FUNCTIONS CONVEX PIECEWISE LINEAR FUNCTIONS GENERAL SUM FUNCTIONS COMPLEX JOB-SHOP SCHEDULING THE JOB-SHOP PROBLEM PROBLEM FORMULATION THE DISJUNCTIVE GRAPH MODEL GENERALIZATIONS JOB-SHOP PROBLEMS WITH FLEXIBLE MACHINES HEURISTIC METHODS JOB-SHOP PROBLEMS WITH TRANSPORT ROBOTS PROBLEMS WITHOUT TRANSPORTATION CON?ICTS PROBLEMS WITH TRANSPORTATION CON?ICTS CONSTRAINT PROPAGATION LOWER BOUNDS JOB-SHOP PROBLEMS WITH LIMITED BU?ERS REPRESENTATION OF SOLUTIONS FLOW-SHOP PROBLEMS WITH INTERMEDIATE BU?ERS JOB-SHOP PROBLEMS WITH PAIRWISE BU?ERS JOB-SHOP PROBLEMS WITH OUTPUT BU?ERS JOB-SHOP PROBLEMS WITH INPUT BU?ERS JOB-SHOP PROBLEMS WITH JOB-DEPENDENT BU?ERS CHAPTER THE RCPSP THE RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM (RCPSP) MAY BE FORMULATED AS FOLLOWS GIVEN ARE N ACTIVITIES (JOBS) I = 1, , N AND R RENEWABLE RESOURCES K = 1, , R A CONSTANT AMOUNT OF RK UNITS OF RESOURCE K IS AVAILABLE AT ANY TIME ACTIVITY I MUST BE PROCESSED FOR PI TIME UNITS DURING THIS TIME PERIOD A CONSTANT AMOUNT OF RIK UNITS OF RESOURCE K IS OCCUPIED ALL DATA ARE ASSUMED TO BE INTEGERS FURTHERMORE, PRECEDENCE CONSTRAINTS ARE DE?NED BETWEEN SOME ACTIVITIES THEY ARE GIVEN BY RELATIONS I ?J, WHERE I ?J MEANS THAT ACTIVITY J CANNOT START BEFORE ACTIVITY I IS COMPLETED THE OBJECTIVE IS TO DETERMINE STARTING TIMES SI FOR THE ACTIVITIES I = 1, , N IN SUCH A WAY THAT AT EACH TIME T THE TOTAL RESOURCE DEMAND IS LESS THAN OR EQUAL TO THE RESOURCE AVAILABILITY OF EACH RESOURCE K = 1, , R, THE GIVEN PRECEDENCE CONSTRAINTS ARE FUL?LLED, I E SI + PI ?SJ IF I ?J, AND THE MAKESPAN CMAX = N MAX I=1 {CI} IS MINIMIZED, WHERE CI := SI + PI IS ASSUMED TO BE THE COMPLETION TIME OF ACTIVITY I THE FACT THAT AN ACTIVITY WHICH STARTS AT TIME SI ?NISHES AT TIME CI = SI + PI IMPLIES THAT ACTIVITIES ARE NOT PREEMPTED WE MAY RELAX THIS CONDITION BY ALLOWING PREEMPTION (ACTIVITY SPLITTING) IN THIS CASE THE PROCESSING OF ANY ACTIVITY MAY BE INTERRUPTED AND RESUMED LATER IT WILL BE STATED EXPLICITLY IF WE CONSIDER MODELS WITH PREEMPTION IT IS OFTEN USEFUL TO ADD A UNIQUE DUMMY STARTING ACTIVITY 0 AND A UNIQUE DUMMY TERMINATION ACTIVITY N + 1, WHICH INDICATE THE START AND THE END OF THE PROJECT, RESPECTIVELY THE DUMMY ACTIVITIES NEED NO RESOURCES AND HAVE PROCESSING TIME ZERO IN ORDER TO IMPOSE 0 ?I ?N + 1 FOR ALL ACTIVITIES I = 1, , N WE SET 0 ?I FOR ALL ACTIVITIES I WITHOUT ANY PREDECESSOR J ?I AND I ?N+1 FOR ALL ACTIVITIES I WITHOUT ANY SUCCESSOR I ?J THEN S0 IS THE STARTING TIME OF THE PROJECT AND SN+1 MAY BE INTERPRETED AS THE MAKESPAN OF THE PROJECT USUALLY WE SET S0 := 0 IF PREEMPTION IS NOT ALLOWED, THE VECTOR S = (SI) DE?NES A SCHEDULE OF THE PROJECT S IS CALLED FEASIBLE IF ALL RESOURCE AND PRECEDENCE CONSTRAINTS ARE FUL- ?LLED WE MAY REPRESENT THE STRUCTURE OF A PROJECT BY A SO-CALLED ACTIVITY-ON-NODE NETWORK G = (V, A), WHERE THE VERTEX SET V := {0, 1, , N, N + 1} CONTAINS ALL ACTIVITIES AND THE SET OF ARCS A = {(I, J) | I, J ?V ; I ?J} REPRESENTS THE PRECEDENCE CONSTRAINTS EACH VERTEX I ?V IS WEIGHTED WITH THE CORRESPONDING PROCESSING TIME PI FOR EACH ACTIVITY I WE DE?NE PRED(I) := {J | (J, I) ?A} AND SUCC(I) := {J | (I, J) ?A} AS THE SETS OF PREDECESSORS AND SUCCESSORS OF ACTIVITY I, RESPECTIVELY ANOTHER REPRESENTATION OF PROJECTS IS BASED ON SO-CALLED ACTIVITY-ON-ARC NET- WORKS WHERE EACH ACTIVITY IS MODELED BY AN ARC SINCE THIS REPRESENTATION HAS SOME DISADVANTAGES, IN MOST CASES ACTIVITY-ON-NODE NETWORKS ARE PREFERRED EXAMPLE 1 1 : CONSIDER A PROJECT WITH N = 4 ACTIVITIES, R = 2 RESOURCES WITH CAPACITIES R1 = 5, R2 = 7, A PRECEDENCE RELATION 2 ?3 AND THE FOLLOWING DATA: I COMPLEX SCHEDULING N QQQQQQQQQ S PPPPPPPP Q S S S S SSW HHH J * P1 = (A) A FEASIBLE SCHEDULE R1 = R2 = (B) AN OPTIMAL SCHEDULE FIGURE 1 1 ILLUSTRATES THE CORRESPONDING ACTIVITY-ON-NODE NETWORK, WHERE THE DUMMY ACTIVITIES 0 AND 5 HAVE BEEN ADDED AND THE VERTICES ARE WEIGHTED WITH THE PROCESSING TIMES IN FIGURE 1 2(A) A SO-CALLED GANTT CHART OF A FEASIBLE SCHEDULE WITH CMAX = 15 IS DRAWN THIS SCHEDULE DOES NOT MINIMIZE THE MAKESPAN, SINCE BY MOVING ACTIVITY 1 TO THE RIGHT, A SHORTER SCHEDULE IS OBTAINED AN OPTIMAL SCHEDULE WITH MAKESPAN CMAX = 12 IS SHOWN IN (B) IN THE FOLLOWING WE WILL DISCUSS DI?ERENT GENERALIZATIONS OF THE RCPSP GENERALIZED PRECEDENCE CONSTRAINTS A PRECEDENCE RELATION I ?J WITH THE MEANING SI + PI ?SJ MAY BE GENERALIZED BY A START-START RELATION OF THE FORM SI + DIJ ?SJ (1 1) WITH AN ARBITRARY INTEGER NUMBER DIJ ?Z THE INTERPRETATION OF RELATION (1 1) DEPENDS ON THE SIGN OF DIJ