Theoretical Analysis Of Algorithms For Typical Shop Scheduling Problems

In a shop scheduling problem, each job requires to be processed on different machines. At a time, each job can be processed on at most one machine, and each machine can process at most one job. The preemption of a job is prohibited. The objective is to determine the sequence and the time of a job on the machines to optimize the required function. As shop scheduling problems are extensive in manufacture and logistics system, and most of them are NP-hard, it has been a main research method to obtain the approximate solution with heuristics for academia and industry. And it is a challenging research topic in scheduling field to analyse and evaluate the performance of heuristic theoretically.This paper investigates two types of shop scheduling problems, flow shop and open shop. New heuristics and associated asymptotic analysis are presented respectively. And some of the existing typical heuristics are performed by both asymptotic analysis and worst case analysis (off-line heuristic) or worst competitive analysis (on-line heuristic). To show the practical effectiveness and convergent speed of these heuristics and lower bounds, numerical experiments are conducted. The content is summarized as follows.1) The Single Job First (SJF) heuristic is presented for flow shop minimizing makespan problem. And it is proved that the heuristic is asymptotically optimal when the problem size goes to infinity. A new lower bound of the problem is given for the further evaluation of the heuristic numerically. The asymptotic optimality of the lower bound is proved and its worst case ratio is the number of machines m, and this bound is tight. At the end of the section, numerical experiments show the asymptotic optimality of the heuristic.2) The Dynamic Single Job First (DSJF) heuristic is presented for flow shop minimizing makespan problem with release dates. And it is proved that the heuristic is asymptotically optimal when the problem size goes to infinity. The asymptotic optimality of First Come First Served (FCFS) manner is obtained as a corollary of the asymptotic analysis of DSJF heuristic. And a new lower bound is given for the problem. The asymptotic optimality of the lower bound is proved and its worst case ratio is the number of machines m, and this bound is tight. At the end of the section, numerical experiments show the the asymptotic optimality of the heuristic and the effectiveness of the lower bound.3) A new lower bound and associated theoretical analysis are presented for flow shop minimizing total weight completion time problem. The theoretical analysis is comprised of asymptotic analysis and worst case analysis. For asymptotic analysis, it is proved that the lower bound is asymptotically optimal when the problem size goes to infinity; for worst case analysis, its worst case ratio is the number of machines m, and this bound is tight. At the end of the section, numerical experiments show the effectiveness of the lower bound.4) Two typical on-line heuristics are used to solve the flow shop minimizing total quadratic time problem with release dates. The first heuristic is Shortest Available Processing Time-First (SPTA-F) and the second heuristic is Shortest Available Processing Time-Average (SPTA-A). It is proved that the two heuristics are both asymptotically optimal when the problem size goes to infinity. And it is pointed out that the worst competitive ratio of SPTA-F is unbounded and the worst competitive ratio of SPTA-A is the square of the number of machines m2, and this bound is tight. With the performance analysis of two lower bounds, a new lower bound which is asymptotically optimal is presented. At the end of the section, numerical experiments show the asymptotic optimality of the two heuristics and the effectiveness of the lower bound.5) The asymptotic optimality of the typical heuristic, Rotation Schedule (RS), is proved for open shop minimizing makespan problem when the problem size goes to infinity. And it is pointed out that the worst case ratio of RS heuristic is the number of machines m, and this bound is tight. And the MRS heuristic based on RS is presented to improve the performance for the moderate problems further. At the end of the section, numerical experiments show the asymptotical optimality of the RS heuristic and the effectiveness of the MRS heuristics.6) The asymptotic optimality of the typical heuristic, Dense Schedule (DS), is proved for open shop minimizing makespan problem with release dates when the problem size goes to infinity. And the Dynamic Shortest Processing Time-Dense Schedule heuristic (DSPT-DS) based on DS is presented to improve the performance for the moderate problems further. At the end of the section, numerical experiments show the effectiveness of the DSPT-DS heuristic.7) The Shortest Processing Time Block (SPTB) heuristic is presented for open shop minimizing total completion time problem. It is proved that the heuristic is asymptotically optimal when the problem size goes to infinity. At the end of the section, numerical experiments show the asymptotic optimality of the heuristic and further computations verify that the presented heuristic is better than the typical matching heuristic.