Minimizing flowtime and maximum earliness on a single machine

Date

1998-02-01

Author

Koksalan, M
Azizoğlu, Meral
Kondakci, SK

Metadata

Show full item record

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

Item Usage Stats

155
views

0
downloads

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 results which demonstrate that the heuristic procedures and the algorithms perform very well.

Subject Keywords

Time, Costs, Algorithm, Tardiness penalties, Bicriterion scheduling problem

URI

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

Journal

IIE TRANSACTIONS

DOI

https://doi.org/10.1023/a:1007470302024

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

Using genetic algorithms for single-machine bicriteria scheduling problems Köksalan, Mustafa Murat; Keha, AB (2003-03-16) 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 probl...
Scheduling jobs on unrelated parallel machines to minimize regular total cost functions Azizoğlu, Meral; Kirca, O (1999-02-01) In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived sp...
Stabilization of the Fast Multipole Method for Low Frequencies Using Multiple-Precision Arithmetic Karaosmanoglu, Bariscan; Ergül, Özgür Salih (2014-08-23) We stabilize a conventional implementation of the fast multipole method (FMM) for low frequencies using multiple-precision arithmetic (MPA). We show that using MPA is a direct remedy for low-frequency breakdowns of the standard diagonalization, which is prone to numerical errors at short distances with respect to wavelength. By increasing the precision, rounding errors are suppressed until a desired level of accuracy is obtained with plane-wave expansions. As opposed to other approaches in the literature, u...
Comparative study on explicit integration algorithms for structural dynamics Çakır, Dilara; Kurç, Özgür; Department of Civil Engineering (2022-8) Conventional explicit integration algorithms used to solve structural dynamic problems may require too small time increments to satisfy the stability requirements in the presence of high-frequency modes. The requirement to have a too small time increment can cause extending the solution time above the tolerable limit. In this study, three different explicit integration algorithms found in the literature are compared in terms of stability, accuracy, and run-time. The examined integration methods are a two-st...
A simulated annealing approach to bicriteria scheduling problems on a single machine Karasakal, Esra (2000-08-01) In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed appro...

Citation Formats

M. Koksalan, M. Azizoğlu, and S. Kondakci, “Minimizing flowtime and maximum earliness on a single machine,” IIE TRANSACTIONS, pp. 192–200, 1998, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/42363.