Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/16897
Title: Evolutionary multi-objective optimization in scheduling problems
Authors: CHEONG CHUN YEW
Keywords: Multi-objective optimization, evolutionary algorithm, scheduling problem, exam timetabling problem, berth allocation problem, vehicle routing problem
Issue Date: 1-Aug-2009
Source: CHEONG CHUN YEW (2009-08-01). Evolutionary multi-objective optimization in scheduling problems. ScholarBank@NUS Repository.
Abstract: The primary aim of this thesis is to present an investigation on the application of multi-objective evolutionary algorithms (MOEAs) to solve a few real-world scheduling problems with vastly different characteristics. Real-world scheduling problems are generally complex, large scale, constrained, and multi-objective in nature that classical operational research techniques are inadequate at solving them effectively. Optimal solutions to these problems in today's productivity-oriented world would have significant economic and social consequences. In this thesis, a generic MOEA framework is devised and problem-specific operators are then designed to adapt the MOEA to solve the different scheduling problems. The research documented in this thesis represents one of the pioneering works on multi-objective optimization of each of the scheduling problems investigated.<br>One of the scheduling problems considered in this thesis is a two-objective exam timetabling problem (ETTP), which involves the scheduling of exams for a set of university courses into a timetable such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as limited seating capacity and no overlapping exams. While existing approaches require prior knowledge of the timetable length in order to be effective, the MOEA proposed in this thesis provides a more general solver to the ETTP by including the timetable length as an optimization objective.<br>A berth allocation problem (BAP), which requires the determination of exact berthing times and positions of incoming ships in a container port, is also studied in this thesis. The BAP considers three objectives of minimizing makespan, waiting time, and degree of deviation from a predetermined priority schedule, which represent the interests of both port and ship operators. The experimental results reveal several interesting relationships between the objectives, justifying the multi-objective approach to the problem, which has never been explored for this problem.<br>This thesis also considers a three-objective vehicle routing problem with stochastic demand (VRPSD), which involves the routing of a set of identical vehicles with limited capacity from a central depot to a set of geographically dispersed customers to satisfy their demands. Unlike the ETTP and the BAP, where all aspects of the problem are known at the point of solving the problem, the VRPSD is a stochastic optimization problem and some problem parameters are uncertain during the solution-searching process. In the VRPSD, the actual demand of each customer is unknown during the routing process but is revealed only when the vehicle reaches the customer. The experimental results show that the solutions obtained by the MOEA are robust to the stochastic nature of the problem.<br>
URI: http://scholarbank.nus.edu.sg/handle/10635/16897
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
CheongCY.pdf4.23 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

353
checked on Dec 11, 2017

Download(s)

282
checked on Dec 11, 2017

Google ScholarTM

Check


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