A genetic algorithm approach for the batch sequencing problem on identical parallel machines | |
| Author | Do Thanh Luu |
| Call Number | AIT Diss. no. ISE-01-2 |
| Subject(s) | Genetic algorithms Economic lot size |
| Note | A dissertation submitted in partial fulfilment of the requirements for the Degree of Doctor of Engineering, School of Advanced Technologies |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-01-02 |
| Abstract | This study aims to investigate an extension of the batch sequencing problem (BSP), a variant of the Lot Sizing Problem, from single machine to identical parallel machine cases. This extension is for scheduling jobs on machines with setups and without tardy jobs and is to minimize the sum of holding and setup costs. The main research issues included a model formulation, feasibility checking for the relaxed problem, the creation of dispatching rules, proposing an application of the model to the due-date setting process, and designing genetic algorithms (GA). The proposed solutions were tested for their efficiency through suitable computational experiments. Two necessary conditions in closed-form expressions and one sufficient condition were found to evaluate the feasibility of the problem without setup time and cost. Dispatching rules were based on the EDD (Earliest Due Date) structure and Greedy heuristics. Linking to the due date assignment problem, the research proved that schedule costs should be included in the due-date/price negotiation process for new jobs. Once this issue is recognized, the model and its solutions are suitable tools. GAs adopted the Swap Mutation and Subschedule Preserved Crossover for genetic operations, Spouse Duplication for forming the mating pool, Roulette Wheel selection and Elitist strategy for the survival selection. A new kind of combination of a dispatching rule and a pure (not hybrid) GA, namely the Gene Bank Strategy, was proposed. The hybrid GA could provide far better results than its two component algorithms. We believe that the combination introduced in the presented hybrid GA could be propagated to other scheduling problems. |
| Year | 2001 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-01-02 |
| Type | Dissertation |
| School | School of Advanced Technologies (SAT) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Bohez, Ir. Erik LJ;Anulark Techanitisawad; |
| Examination Committee(s) | Batanov, Dentcho N ;Weijters, A.J.M.M. ; |
| Scholarship Donor(s) | DAAD, Germany ; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology,2001 |