A heuristic approach to bicriteria scheduling

Date

1999-10-01

Author

Köksalan, Mustafa Murat

Metadata

Show full item record

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

Item Usage Stats

189
views

0
downloads

We consider the problem of sequencing jobs on a single machine while minimizing a nondecreasing function of two criteria. We develop a heuristic procedure that quickly finds a good solution for bicriteria scheduling. The procedure is based on using several arcs in the criterion space that are representative of the possible locations of nondominated solutions. By sampling a small number of points on these arcs, a promising point is identified in the criterion space for each are. An efficient sequence in the neighborhood of each of the promising points is found and the best of these efficient sequences is selected as the heuristic solution. We implement the procedure for two different bicriteria scheduling problems: (i) minimizing total flowtime and maximum tardiness and (ii) minimizing total flowtime and maximum earliness. The computational experience on a wide variety of problem instances show that the heuristic approach is very robust and yields good solutions. (C) 1999 John Wiley & Sons, Inc.

Subject Keywords

Management Science and Operations Research, General Engineering, Modelling and Simulation, Ocean Engineering

URI

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

Journal

NAVAL RESEARCH LOGISTICS

DOI

https://doi.org/10.1002/(sici)1520-6750(199910)46:7<777::aid-nav2>3.0.co;2-5

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A New Outranking-Based Approach for Assigning Alternatives to Ordered Classes Köksalan, Mustafa Murat; Mousseau, Vincent; Ozpeynirci, Oezguer; Ozpeynirci, Selin Bilgin (Wiley, 2009-02-01) We consider the problem of assigning alternatives evaluated on several criteria into ordered categories C(1), C(2), ..., C(p). This problem is known as the multi-criteria sorting problem and arises in many situations such as classifying countries into different risk levels based on economical and socio-political criteria, evaluating credit applications of bank customers. We are interested in sorting methods that are grounded on the construction Of Outranking relations. Among these, the Electre Tri method re...
An interactive procedure for selecting acceptable alternatives in the presence of multiple criteria Ulu, C; Köksalan, Mustafa Murat (Wiley, 2001-10-01) In this paper, we consider the multiple criteria decision-making problem of partitioning alternatives into acceptable and unacceptable sets. We develop interactive procedures for the cases when the underlying utility function of the decision maker is linear, quasiconcave, and general monotone. We present an application of the procedures to the problem of admitting students to the master's degree program at the Industrial Engineering Department, Middle East Technical University. (C) 2001 John Wiley & Sons, Inc.
An interactive sorting method for additive utility functions Koeksalan, Murat; Oezpeynirci, Selin Bilgin (Elsevier BV, 2009-09-01) In this paper, we consider the problem of placing alternatives that are defined by multiple criteria into preference-ordered categories. We consider a method that estimates an additive utility function and demonstrate that it may misclassify many alternatives even when substantial preference information is obtained from the decision maker (DM) to estimate the function. To resolve this difficulty, we develop an interactive approach. Our approach occasionally requires the DM to place some reference alternativ...
Constructing a strict total order for alternatives characterized by multiple criteria: An extension Dehnokhalaji, Akram; Korhonen, Pekka J.; Köksalan, Mustafa Murat; Nasrabadi, Nasim; Ozturk, Diclehan Tezcaner; Wallenius, Jyrki (Wiley, 2014-03-01) The problem of finding a strict total order for a finite set of multiple criteria alternatives is considered. Our research extends previous work by us, which considered finding a partial order for a finite set of alternatives. We merge the preference information extracted from the preference cones and corresponding polyhedral sets, with the information derived from pairwise comparisons of two alternatives, yielding a preference matrix. This preference matrix is used as input to an integer programming model ...
An approach for solving discrete alternative multiple criteria problems involving ordinal criteria Köksalan, Murat; Karwan, Mark H.; Zionts, Stanley (Wiley, 1988-12) The existence of ordinal criteria is a factor that complicates multiple criteria problems. In this article we develop an approach for the problem of choosing among discrete alternatives assuming that criteria are ordinal. The approach requires pairwise comparisons of alternatives by the decision maker. Based on these comparisons, presumably inferior alternatives are eliminated. Experience on randomly generated problems indicates that the approach usually chooses one of the most preferred alternatives and re...

Citation Formats

M. M. Köksalan, “A heuristic approach to bicriteria scheduling,” NAVAL RESEARCH LOGISTICS, pp. 777–789, 1999, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/57839.