Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/15438
Title: Algorithms for scheduling problems with weighted earliness-tardiness penalty
Authors: FENG GUANG
Keywords: FPTAS, SWO, Timetabling, Earliness-Tardiness Scheduling
Issue Date: 30-May-2006
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/15438
Appears in Collections:Master's Theses (Open)

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

OPEN

NoneView/Download

Page view(s)

250
checked on Dec 18, 2017

Download(s)

150
checked on Dec 18, 2017

Google ScholarTM

Check


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