A simulated annealing approach to bicriteria scheduling problems on a single machine

Date

2000-08-01

Author

Karasakal, Esra

Metadata

Show full item record

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

Item Usage Stats

48
views

0
downloads

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 approach yields solutions that are very close to lower bounds and hence very close to the optimal solutions of their corresponding problems for the minimization of total flowtime and maximum earliness. For the minimization of total flowtime and number tardy, our experiments show that the simulated annealing approach yields results that are superior to randomly generated schedules.

Subject Keywords

Simulated annealing, Heuristics, Single machine scheduling, Bicriteria scheduling, Flowtime, Maximum earliness, Number of tardy jobs

URI

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

Journal

JOURNAL OF HEURISTICS

DOI

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

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

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 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 fast and optimal static segment scheduling method for FlexRay v3.0 ÇAKMAK, CUMHUR; Schmidt, Şenan Ece; Schmidt, Klaus Verner (2017-06-29) We propose a novel and fast frame scheduling method for the Static Segment (SS) of the new in-vehicle network standard FlexRay v3.0 in this paper. The proposed methods assigns frames to the SS using the minimum number of time slots based on an Integer Linear Programming formulation. Different. from the existing method in the literature, the proposed method computes optimal frame schedules within miliseconds.
A modified algorithm for peer-to-peer security Akleylek, Sedat; Emmungil, Levent; NURİYEV, URFAT (2007-01-01) In this paper we present the steganographic approach to peer-to-peer systems with a modified algorithm. This gives the user a very high level of protection against being compelled to disclose its contents. Even the realization of the quantum computer cannot solve NP-hard problem in a polynomial time, a modified algorithm with steganographic use depending on Knapsack problem may make peer-to-peer systems secure.
A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem Tozkapan, A; Kirca, O; Chung, CS (2003-02-01) In this paper, a two-stage assembly scheduling problem is considered with the objective of minimizing the total weighted flowtime. A lower bounding procedure and a dominance criterion are developed and incorporated into a branch and bound procedure. A heuristic procedure is also used to derive an initial upper bound. Computational results of the algorithm are presented.

Citation Formats

E. Karasakal, “A simulated annealing approach to bicriteria scheduling problems on a single machine,” JOURNAL OF HEURISTICS, pp. 311–327, 2000, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/40064.