Using genetic algorithms for single-machine bicriteria scheduling problems

Date

2003-03-16

Author

Köksalan, Mustafa Murat
Keha, AB

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

125
views

0
downloads

We consider two bicriteria scheduling problems on a single machine: minimizing flowtime and number of tardy jobs, and minimizing flowtime and maximum earliness. Both problems are known to be NP-hard. For the first problem, we developed a heuristic that produces an approximately efficient solution (AES) for each possible value the number of tardy jobs can take over the set of efficient solutions. We developed a genetic algorithm (GA) that further improves the AESs. We then adapted the GA for the second problem by exploiting its special structure. We present computational experiments that show that the GAs perform well. Many aspects of the developed GAs are quite general and can be adapted to other multiple criteria scheduling problems.

Subject Keywords

Bicriteria scheduling, Genetic algorithms

URI

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/s0377-2217(02)00220-5

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Minimizing flowtime and maximum earliness on a single machine Koksalan, M; Azizoğlu, Meral; Kondakci, SK (1998-02-01) We consider the bicriteria scheduling problem of minimizing flowtime and maximum earliness on a single machine. The problem is known to be NP-hard. We develop heuristic procedures for generating all efficient sequences for the cases where machine idle time is either allowed or not allowed. For both cases we also discuss an algorithm that finds the best of the approximately efficient sequences for a given objective function by generating only a small subset of those sequences. We present computational result...
On the minimization of total weighted flow time with identical and uniform parallel machines Azizoğlu, Meral (1999-02-16) We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.
Hybrid meta-heuristic algorithms for the resource constrained multi-project scheduling problem Uysal, Furkan; Sönmez, Rifat; Department of Civil Engineering (2014) The general resource constrained multi-project scheduling problem (RCMPSP) consists of simultaneous scheduling of two or more projects with common resource constraints, while minimizing duration of the projects. Critical Path Method and other scheduling methods do not consider resource conflicts and practically used commercial project management software packages and heuristic methods provide very limited solutions for the solution of the RCMPSP. Considering the practical importance of multi-project schedul...
Hybrid heuristic algorithms for the multi objective load balancing of 2D bin packing problems Muhammet, Beyaz; Dökeroğlu, Tansel; Coşar, Ahmet (null; 2015-09-23) 2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Multiobjective versions of this well-known industrial engineering problem can occur frequently in real world application. Recently, Hybrid Evolutionary Algorithms have appear as a new area of research with their ability to combine alternative heuristics and local search mechanisms together for higher quality solutions. In this study, we propose a set of novel multiobjective hybrid genetic and memetic algorithms that make use of...
Scheduling with bicriteria: total flowtime and number of tardy jobs Kondakci, SK; Bekiroglu, T (1997-11-06) In this paper the problem of minimizing total flowtime and number of tardy jobs on a single machine is considered. Some properties of the nondominated solutions are discussed. Computational results on the usefulness of developed properties for problems having up to 30 jobs are reported.

Citation Formats

M. M. Köksalan and A. Keha, “Using genetic algorithms for single-machine bicriteria scheduling problems,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 543–556, 2003, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57336.