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

Download
2013
Kaya, Süleyman
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.

Suggestions

Uniform Parallel machine scheduling with family set-up times
Tamer, Meral; Azizoğlu, Meral; Azizoğlu, Meral; Department of Industrial Engineering (2003)
In this study, we address the scheduling problem of uniform parallel machines with family set-up times so as to minimize the total completion time. We develop a branch and jound algorithm that employs an efficient branching scheme. A bounding mechanism is jroposed to increase the efficiency of this algorithm. Our computational experiment shows hat the optimal solution is found in reasonable CPU times up to 15 jobs. Further experiments »re conducted to test the bounding mechanisms and this experiment indicat...
A heuristic approach for the single machine scheduling tardiness problems
Özbakır, Saffet İlker; Kırca, Ömer; Department of Industrial Engineering (2011)
In this thesis, we study the single machine scheduling problem. Our general aim is to schedule a set of jobs to the machine with a goal to minimize tardiness value. The problem is studied for two objectives: minimizing total tardiness value and minimizing total weighted tardiness value. Solving optimally this problem is difficult, because both of the total tardiness problem and total weighted tardiness problem are NP-hard problems. Therefore, we construct a heuristic procedure for this problem. Our heuristi...
A fixed job scheduling problem with machine-dependent job weights
Eliiyi, D. T.; Azizoğlu, Meral (2009-01-01)
This study considers the identical parallel machines operational fixed job scheduling problem with machine-dependent job weights. A job is either processed in a fixed interval or is not processed at all. Our aim is to maximise the total weight of the processed jobs. We show that the problem with machine eligibility constraints resides as a special case of this problem. We identify some special polynomially solvable cases and propose a branch-and-bound (BB) algorithm that employs efficient bounding schemes a...
A bicriteria rescheduling problem on unrelated parallel machines : network flow and enumeration based approaches
Özlen, Melih; Azizoğlu, Meral; Department of Industrial Engineering (2006)
This study considers bicriteria approaches to the minimum cost network flow problem and a rescheduling problem where those approaches find their applications. For the bicriteria integer minimum cost network flow problem, we generate all efficient solutions in two phases. The first phase generates the extreme supported efficient points that are the extreme points of the objective space of the continuous bicriteria network flow problem. In the second phase, we generate the nonextreme supported and unsupported...
A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems
Chung, Chia-Shin; Flynn, James; Kırca, Ömer (Elsevier BV, 2006-10-01)
The m-machine permutation flowshop problem with the total tardiness objective is a common scheduling problem, which is known to be NP-hard. Here, we develop a branch and bound algorithm to solve this problem. Our algorithm incorporates a machine-based lower bound and a dominance test for pruning nodes. We undertake a numerical study that evaluates our algorithm and compares it with the best alternative existing algorithm. Extensive computational experiments indicate that our algorithm performs better and ca...
Citation Formats
S. Kaya, “A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times,” M.S. - Master of Science, Middle East Technical University, 2013.