Algorithms for scheduling problems with weighted earliness-tardiness penalty

Abstract

In this thesis, we study the scheduling problems with earliness-tardiness penalty from three aspects. Firstly, we discuss how to approximate a class of restrictive scheduling problems. Our most significant contribution is to provide a scheme that can transform a restrictive scheduling problem with certain structure into a polynomial number of unrestrictive sub-problems, such that the original restrictive scheduling problem has fully polynomial approximations schemes. Secondly, we discussed how to improve the performance of the algorithm for single machine scheduling problems with a fixed execution sequence. This problem has been widely used as a sub-algorithm for more complex scheduling problems with earliness-tardiness penalty. Our contribution is to combine the strengths of two distinctive algorithms, and produce a better performing algorithm. Our last research objective is to apply squeak wheel optimization framework to a very complex class of scheduling problems. We have showed that it can be more effective than traditional meta-heuristics, such as simulated annealing. We implemented our algorithms and presented some benchmarking results.