Please use this identifier to cite or link to this item:
Title: Algorithms for scheduling problems with weighted earliness-tardiness penalty
Keywords: FPTAS, SWO, Timetabling, Earliness-Tardiness Scheduling
Issue Date: 30-May-2006
Citation: FENG GUANG (2006-05-30). Algorithms for scheduling problems with weighted earliness-tardiness penalty. ScholarBank@NUS Repository.
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.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
thesis16.pdf491.14 kBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.