Interval Scheduling With Sequence-dependent Setup Times

Developing effective and accurate scheduling algorithms is an important topic in Combinatorial Optimization.Scheduling policy can be determined to optimize the selected performance indicators with limited resources and various constraints,which can potentially improve the economic benefits.This thesis considers the scheduling problem on identical parallel machines with release dates and deadlines to determine the processing policy to minimize the number of machines needed.Interval scheduling with sequence dependent setup times is mainly studied in term of algorithm and complexity.In this thesis,we firstly study the fixed job scheduling problem and propose a list scheduling algorithm to solve in O(n~2)time and then give the improved O(n log n)algorithm.Combining with scheduling problems in real life,this thesis introduces the constraint of sequence dependent setup times and analyze the connection between this scheduling problem and fixed job scheduling.We develop a polynomial-time iterative algorithm to solve this problem.By constructing the corresponding directed job digraph with transitive arcs,the scheduling problem is transformed to the network optimization problem,and thus the correctness of the algorithm is proved based on the knowledge of matching and path covering.Finally,the general case without the triangle inequality constraints for setup times is considered.This case is transformed into a specific structural graph and network.Exact and efficient techniques are proposed to solve the problem by adjusting the polynomial-time algorithms of network optimization.Then the minimum network flow techniques are generalized to solve multiple job categories scheduling.