ALGORITHMS FOR SEQUENCING AND SCHEDULING

1 IBRAHIM M. ALHARKAN ALGORITHMS FOR SEQUENCING AND SCHEDULING ALGORITHMS for SEQUENCING and SCHEDULING Ibrahim M. Alharkan Industrial Engineering Department College of Engineering King Saud University Riyadh, Saudi Arabia Chapter 1. SCHEDULING Theory Introduction 1. 2 Definitions 1. 3 Levels of the SEQUENCING and SCHEDULING Problem 1. 4 SCHEDULING Environments 1. 5 Assumptions 1.

2 6 Categories of SCHEDULING Problems 1. 7 SCHEDULING Framework & Notations 1. 7 Decision-Making Goal 1. 9 Criteria of the SEQUENCING And SCHEDULING 1. 10 Criteria based on completion Criteria based on inventory and machine utilization Criteria based on due-dates. Method of Solution 1.

3 13 Dispatching Rules 1. 13 Effect of dispatching rules: Chapter 2. Single Machine SCHEDULING Introduction 2. 2 SCHEDULING Mathematics 2. 2 Gantt chart Minimization of maximum Lateness problem (1||Lmax) 2. 7 Minimization of Total Weighted completion time problem (1|| jCj) Minimization of Total Weighted completion time problem with Precedence Relations (1| prec| jCj) Non-Preemptive SCHEDULING 2.

4 13 Preemptive SCHEDULING 2. 14 Number of Tardy Jobs (1||nt) 2. 16 Branch & Bound Method 2. 18 Minimization of maximum lateness with ready time Problem (1 | rj | Lmax ) 2. 19 Minimization of total weighted tardiness Problem (1 || jTj) 2. 27 Minimization of maximum lateness with precedence problem (1 | prec | Lmax) 2. 31 Chapter 3. Parallel Machine SCHEDULING Introduction 3.

5 2 Minimization of Makespan problem (Pm || Cmax) 3. 2 Longest Processing Time first (LPT) Rule Minimization of Makespan with precedence (Pm | prec | Cmax) Problem 3. 7 Minimization of Makespan with Pj =1 and precedence problem (Pm | Pj = 1, tree | Cmax) 3. 9 Contents Contents ALGORITHMS for SEQUENCING & SCHEDULING ii CP Rule LNS Rule Minimization of Makespan with preemption (Pm | prmp | Cmax) 3. 17 Longest Remaining Processing time first LRPT Rule For (Pm | prmp | Cmax) 3. 18 Minimization of Makespan for machines with different speed and with preemption (Qm | prmp | Cmax) 3. 20 Minimization of total completion time for machines with different speed and with preemption (Qm | prmp | Cj) 3.

6 21 Minimization of total maximum lateness with preemption (Pm | prmp | Lmax) 3. 24 Chapter 4. Flow shop SCHEDULING Introduction 4. 2 Minimization of makespan using Johnson s Rule for (F2 || Cmax) Problem 4. 3 Minimization of Makespan for (F3 || Cmax ) Problem 4. 5 Minimization of makespan for (Fm || Cmax ) problems when M > 3 4. 7 Permutation Schedules 4. 8 Heuristics to be used for minimization of makespan for (Fm || Cmax) Problems 4.

7 8 Palmer s Heuristic Campbell, Dudek, and Smith (CDS) Algorithm Enscor, and Ham (NEH) Algorithm Branch and Bound Algorithm 4. 20 Chapter 5. Job Shop SCHEDULING Introduction 5. 2 Earliest Start Time (EST) Schedule Generation 5. 2 Shifting Bottleneck (SB) Heuristic 5.

8 7 Chapter 6. project Management and SCHEDULING Introduction 6. 2 Planning the project 6. 3 Executing the project 6. 4 Monitor Control Closing project SCHEDULING 6. 5 critical path Method 6.

9 6 CPM Calculations AON Network Computations PERT Methodology 6. 17 Time / Cost Trade-off 6. 24 Types of cost Crashing of project Time-Cost Trade-off Assumptions Contents ALGORITHMS for SEQUENCING & SCHEDULING iii Additional Consideration Chapter 7. Resource Constrained project SCHEDULING Introduction 7. 2 Resource Allocation In project 7.

10 3 Resource-Constrained SCHEDULING 7. 3 Resource Allocation Rules 7. 4 Categorization Of Resource SCHEDULING Techniques 7. 9 Single-Resource Multi-Capacity SCHEDULING 7. 9 Multiple-Resource Single Capacity SCHEDULING 7.