Fixed job scheduling on uniform parallel machines

Download

143204.pdf

Date

2003

Author

Bekki, Özgün Barış

Metadata

Show full item record

Item Usage Stats

139
views

0
downloads

In this study, a fixed job scheduling problem on uniform parallel machines is considered. The objective function is the maximization of the total weight of the jobs processed. We show that it is NP-hard and develop polynomial time algo rithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and powerful lower and upper bounding proce dures. Computational analysis is conducted to investigate the effects of changing certain parameters on the difficulty of the problem. The results have revealed that the algorithm finds solutions to large sized problem instances in reasonable times.

Subject Keywords

Fixed job scheduling, Uniform machines, Total weight

URI

https://hdl.handle.net/11511/13603

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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 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...
Operational fixed job scheduling problem Türsel Eliiyi, Deniz; Azizoğlu, Meral; Department of Industrial Engineering (2004) In this study, we consider the Operational Fixed Job Scheduling Problem on identical parallel machines. The problem is to select a subset of jobs for processing among a set of available jobs with fixed arrival times and deadlines, so as to maximize the total weight. We analyze the problem under three environments: Working time constraints, Spread time constraints, and Machine dependent job weights. We show that machine eligibility constraints appear as a special case of the last environment. We settle the c...
A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times Kaya, Süleyman; Meral, Fatma Sedef; Department of Industrial Engineering (2013) 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 complet...
Spread time considerations in operational fixed job scheduling Eliiyi, D. T.; Azizoğlu, Meral (Informa UK Limited, 2006-10-15) In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance c...

Citation Formats

Ö. B. Bekki, “Fixed job scheduling on uniform parallel machines,” M.S. - Master of Science, Middle East Technical University, 2003.