A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times


Thesis Type: Postgraduate

Institution Of The Thesis: Middle East Technical University, Faculty of Engineering, Department of Industrial Engineering, Turkey

Approval Date: 2013

Thesis Language: English

Student: Süleyman Kaya

Supervisor: FATMA SEDEF MERAL

Abstract:

The scheduling problem considered in this study is the integration of two different problems in the scheduling area. One of the problems is the resource constrained project scheduling problem with renewable resources, while the other one is the single machine scheduling problem with sequence dependent setup times. In real life, project scheduling problems are usually complicated and include various scheduling problems characteristics. The objective of the problem addressed is the minimization of the completion time of the project. A genetic algorithm and a MIP model are developed for the problem. The results of the genetic algorithm for small problem instances are compared with the results of the M IP model coded using the library of IBM ILOG CPLEX. The MIP model developed is the integration of the MIP model of the resource constrained project scheduling problem and the MIP model of the single machine scheduling with sequence dependent setup times. For big problem instances, results are compared with the results of hill-climbing-like search algorithm. Computer programs for the genetic algorithm, MIP model and the hill-climbing-like search algorithm are coded by Microsoft Visual C# .Net platform. The results obtained by the proposed genetic algorithm are always superior to the hill-climbing-like search algorithm’s results.