Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
172
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.