← Back to Search

Get Citationsy

DOI: 10.1051/ro:2001109

# Multicriteria Scheduling Problems: A Survey

V. T'kindt, J. Billaut

Published 2001 · Computer Science

Save to my Library

Download PDF

Download via 🐼 PaperPanda
Download via oaDOI
Download via OAB
Download via LibKey
Download via Google
Google Scholar

Analyze on Scholarcy
Visualize in Litmaps
Share

Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager

Time to take this seriously.

This paper presents a state-of-the-art survey on multicriteria scheduling and introduces a definition of a multicriteria scheduling problem. It provides a framework that allows to tackle multicriteria scheduling problems, according to Decision Aid concepts. This problem is decomposed into three different problems. The first problem is about obtaining a model. The second one is how to take criteria into account and the third one is about solving a scheduling problem. An extension to an existing notation for scheduling problems is proposed for multicriteria scheduling problems. Then, basic results from the literature on multicriteria optimization are presented. These results are used to build the final scheduling problem to solve. Finally a survey is presented for one-machine, parallel machines and flowshop multicriteria scheduling problems.

This paper references

10.1002/NAV.3800030106

Various optimizers for single‐stage production

W. Smith (1956)

10.1016/0022-247X(68)90201-1

Proper efficiency and the theory of vector maximization

A. Geoffrion (1968)

10.1109/TSMC.1971.4308298

On a bicriterion formation of the problems of integrated system identification and system optimization

Yv Haimes Yv (1971)

10.1002/NAV.3800190215

A note on the extension of a result on scheduling with secondary criteria

Horace W. Heck (1972)

Vector optimization for control with performance and parameter sensitivity indices

F. Gembicki (1974)

10.1002/NAV.3800220317

A note on a scheduling problem with dual criteria

H. Emmons (1975)

10.1002/NAV.3800220314

One machine sequencing to minimize mean flow time with minimum number tardy

H. Emmons (1975)

10.1002/NAV.3800230111

Scheduling to minimize the weighted sum of completion times with secondary criteria

R. Burns (1976)

10.1007/978-3-642-87563-2_5

On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple-Criteria Objectives

V. Bowman (1976)

10.1287/opre.25.1.62

Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties

J. B. Sidney (1977)

10.1287/opre.26.6.1079

Technical Note - Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties

S. Lakshminarayan (1978)

10.1016/0377-2217(78)90043-7

Four solution techniques for a general one machine scheduling problem: A comparative study

L. V. Wassenhove (1978)

10.1111/J.1540-5915.1979.TB00004.X

MULTICRITERIA OPTIMIZATION: A GENERAL CHARACTERIZATION OF EFFICIENT SOLUTIONS*

R. Soland (1979)

10.1007/978-3-642-48782-8_32

The Use of Reference Objectives in Multiobjective Optimization

A. Wierzbicki (1979)

10.1080/05695558008974515

Two Single Machine Sequencing Problems Involving Controllable Job Processing Times

R. Vickson (1980)

10.1016/0377-2217(80)90087-9

Single machine scheduling to minimize weighted sum of completion times with secondary criterion -- A branch and bound approach

S. Bansal (1980)

10.1287/opre.28.5.1155

Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine

R. Vickson (1980)

10.1016/0377-2217(80)90038-7

Solving a bicriterion scheduling problem

L. V. Wassenhove (1980)

10.15807/JORSJ.24.37

ONE MACHINE SCHEDULING PROBLEM WITH DUAL CRITERIA

S. Miyazaki (1981)

10.1002/NAV.3800280411

Minimizing the average deviation of job completion times about a common due date

J. J. Kanet (1981)

10.1287/opre.29.1.146

Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs

J. Barnes (1981)

10.1080/00207548108956667

Optimal assignment of due-dates for a single processor scheduling problem

A. Seidmann (1981)

10.1287/opre.30.2.391

Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem

S. S. Panwalkar (1982)

10.1016/S0377-2217(82)80008-8

A bicriterion approach to time/cost trade-offs in sequencing

L. V. Wassenhove (1982)

10.1080/05695558308974617

A Branch-and-Bound Procedure to Solve a Bicriterion Scheduling Problem

Sen Tapan (1983)

10.1007/BF00934608

Hybrid algorithm for sequencing with bicriteria

K. Lin (1983)

10.1016/0167-188X(83)90012-5

Minimizing a quadratic function of job lateness on a single machine

S. Gupta (1983)

10.1016/0305-0548(83)90018-7

Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number

J. Shanthikumar (1983)

10.1002/NAV.3800310214

Minimizing the sum of absolute lateness in single‐machine and multimachine scheduling

P. S. Sundararaghavan (1984)

10.1287/MNSC.30.11.1268

An Overview of Techniques for Solving Multiobjective Mathematical Programs

G. W. Evans (1984)

Single machine scheduling to minimize weighted completion time with maximum allowable tardiness, Research report

S Chand (1984)

Single machine scheduling to minimize weighted completion time with maximum allowable tardiness

S. Chand (1984)

Méthodologie multicritère d'aide à la décision

B. Roy (1985)

10.1287/MNSC.32.4.464

Scheduling with multiple performance measures: the one-machine case

R. Nelson (1986)

10.1002/NAV.3800330319

A note on the single-machine scheduling problem with minimum weighted completion time and maximum allowable tardiness

S. Chand (1986)

10.1057/JORS.1986.197

A Mixed-Integer Goal-Programming Formulation of the Standard Flow-Shop Scheduling Problem

W. Selen (1986)

10.1002/NAV.3800330206

MINIMIZING MEAN ABSOLUTE DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE.

U. Bagchi (1986)

10.1016/0167-188X(86)90007-8

Bi-criterion single-machine scheduling with forbidden early shipments

T. Fry (1986)

Multiple criteria optimization: Theory

R. Steuer (1986)

A mixed integer goal-programming formulation of a flowshop scheduling problem

W. Selen (1986)

10.1016/0305-0483(87)90015-6

Single machine scheduling: A comparison of two solution procedures

T. Fry (1987)

10.1016/0305-0548(87)90033-5

A BI-criterion approach to minimizing inventory costs on a single machine when early shipments are forbidden

T. Fry (1987)

10.1002/1520-6750(198710)34:5<739::AID-NAV3220340513>3.0.CO;2-3

Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date

U. Bagchi (1987)

10.1287/MNSC.33.7.894

Minimizing Mean Squared Deviation of Completion Times About a Common Due Date

U. Bagchi (1987)

10.1080/07408178708975418

Minimizing Weighted Absolute Deviation in Single Machine Scheduling

T. Fry (1987)

10.1002/1520-6750(198712)34:6<803::AID-NAV3220340605>3.0.CO;2-2

Scheduling to a common due date on parallel uniform processors

H. Emmons (1987)

10.1080/00207548808947840

Filtered beam search in scheduling

P. Ow (1988)

10.1080/00207548808948000

Planning for idle time: A rationale for underutilization of capacity

T. Fry (1988)

10.1016/0377-2217(88)90356-6

Single machine scheduling to minimize weighted earliness subject to no tardy jobs

S. Chand (1988)

10.1016/0305-0483(88)90008-4

Bicriterion static scheduling research for a single machine

P. Dileepan (1988)

10.1287/MNSC.34.2.254

A branch-and-bound approach to the bicriterion scheduling problem invloving total flowtime and range of lateness

T. Sen (1988)

10.1080/00207548808947888

Determination of an optimal common due date and optimal sequence in a single machine job shop

C. R. Bector (1988)

10.1287/moor.13.2.330

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties

M. Garey (1988)

10.1057/jors.1988.149

Multiple Criteria Optimisation: Theory, Computation and Application

R. S. Laundy (1988)

10.1057/JORS.1989.58

Alternative Formulations of a Flow-shop Scheduling Problem

J. M. Wilson (1989)

10.1287/MNSC.35.2.177

The single machine early/tardy problem

P. Ow (1989)

10.1016/0305-0483(89)90063-7

A framework for single machine multiple objective sequencing research

T. Fry (1989)

10.1002/1520-6750(198910)36:5<663::AID-NAV3220360510>3.0.CO;2-X

Single-machine scheduling to minimize absolute deviation of completion times from a common due date

W. Szwarc (1989)

10.1016/0305-0548(89)90034-8

Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty

T. C. John (1989)

10.1137/0218022

Minimizing Schedule Length Subject to Minimum Flow Time

J. Leung (1989)

10.1002/1520-6750(199012)37:6<981::AID-NAV3220370617>3.0.CO;2-H

Multiobjective flow-shop scheduling

R. Daniels (1990)

10.1016/0305-0548(90)90022-Y

Scheduling unit processing time jobs on a single machine with multiple criteria

Chuen-Lung Chen (1990)

10.1080/07408179008964183

Minimizing the Weighted Sum of Late and Early Completion Penalties in a Single Machine

Mesbah U. Ahmed (1990)

10.1016/0167-188X(91)90008-P

Bicriterion jobshop scheduling with total flowtime and sum of squared lateness

P. Dileepan (1991)

10.1057/JORS.1992.126

Two-Stage Flowshop Scheduling Problem with Bicriteria

C. Rajendran (1992)

Single-machine bicriteria scheduling

J. Hoogeveen (1992)

10.1016/0377-2217(93)90245-I

Two parallel machine sequencing problems involving controllable job processing times

B. Alidaee (1993)

10.1142/9789814354363_0013

Complexity of Single Machine Hierarchical Scheduling: A Survey

Chung-Yee Lee (1993)

10.1016/0377-2217(93)90236-G

Complexity of single machine, multi-criteria scheduling problems

Chuen-Lung Chen (1993)

Complexity of single machine

C.-L. Chen (1993)

10.1016/0360-8352(94)90337-9

A simulated annealing heuristic for scheduling in a flowshop with bicriteria

Rajesh Gangadharan (1994)

10.1080/00207549408957083

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

C. Rajendran (1994)

10.1057/JORS.1994.106

Parallel-Machine Scheduling Problems with Earliness and Tardiness Penalties

T.C.E. Cheng (1994)

10.1002/1520-6750(199402)41:1<33::AID-NAV3220410104>3.0.CO;2-S

The parallel machine min-max weighted absolute lateness scheduling problem

Chung-Lun Li (1994)

Complexity of multiple machines, multi-criteria scheduling problems

C.-L Chen (1994)

Complexity of multiple machines

C.-L. Chen (1994)

On the Methodology of Multiobjective Optimization with Applications

K. Miettinen (1994)

10.1016/0377-2217(93)E0212-G

Heuristics for scheduling in flowshop with multiple objectives

C. Rajendran (1995)

10.1016/0167-6377(95)00023-D

Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time

H. Hoogeveen (1995)

10.1016/0377-2217(93)E0140-S

Multiple and bicriteria scheduling : A literature survey

A. Nagar (1995)

Problème industriel d'ordonnancement bicritère sur machine unique : modélisation et aide à la décision

V. Bourgade (1995)

10.1080/00207549508930220

A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem

S. H. Zegordi (1995)

10.1057/JORS.1995.102

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

A. Nagar (1995)

10.1287/ijoc.7.1.63

Scheduling n Independent Jobs on m Uniform Machines with both Flowtime and Makespan Objectives: A Parametric Analysis

S. McCormick (1995)

Probì eme industriel d'ordonnancement bicritère sur machine unique : modélisation et aidè a la décision

V Bourgade (1995)

Solving κ-stage hybrid flowshop scheduling problems

A. Vignier (1996)

10.1016/0377-2217(94)00191-X

Scheduling jobs with different, job-dependent earliness and tardiness penalties using the SLK method

G. Adamopoulos (1996)

10.1016/0377-2217(95)00275-8

Genetic algorithms for the two-stage bicriteria flowshop problem

Venkata Ranga Neppalli (1996)

10.1016/0377-2217(95)00133-6

Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs

Z. Chen (1996)

10.1016/0377-2217(95)00116-6

Single-machine scheduling with time windows and earliness/tardiness penalties

C. Koulamas (1996)

10.1007/978-3-642-60667-0_27

Bicriteria Scheduling: Minimizing Flowtime and Maximum Earliness on a Single Machine

M. Azizoglu (1997)

10.1023/A:1018913902852

Single machine hierarchical scheduling with customer orders and multiple job classes

J. Gupta (1997)

10.1057/PALGRAVE.JORS.2600442

Bicriterion scheduling in the two-machine flowshop

C. Liao (1997)

10.1057/palgrave.jors.2600793

Scheduling Computer and Manufacturing Processes

J. Blazewicz (1997)

10.1007/978-3-642-59132-7_70

Scheduling of Unit Processing Time Jobs on a Single Machine

Suna Kondakci (1997)

10.1080/002075497195344

Scheduling job families about an unrestricted common due date on a single machine

M. Azizoglu (1997)

Bicriteria scheduling hybrid flowshop problems

F. Riane (1997)

Un algorithme optimal polynomial pour résoudre unprobì eme d'ordonnancement bicritèrè a machinesparalì eles

V T 'kindt (1997)

Meslet, Un algorithme optimal polynomial pour résoudre un problème d’ordonnancement bicritère à machines parallèles, in Conference on Automation-Computers Engineering-Image-Signal (AGIS’97)

V. T’kindt (1997)

Billaut, Resolution of a 2-machine bicriteria flowshop scheduling problem, in Int. Conference on Methods and Applications of Multicriteria Decision Making (MAMDM’97)

V. T’kindt (1997)

Multiple Criteria Optimization: Classification and Methodology

M. Ehrgott (1997)

Resolution of a 2-machine bicriteria flowshop scheduling problem

V T 'kindt (1997)

10.1080/002075498192689

A GENETIC ALGORITHM FOR SCHEDULING JOB FAMILIES ON A SINGLE MACHINE WITH ARBITRARY EARLINESS/TARDINESS PENALTIES AND AN UNRESTRICTED COMMON DUE DATE

S. Webster (1998)

10.1016/S0377-2217(97)00338-X

A bicriteria two-machine permutation flowshop problem

Funda Sivrikaya-Serifoglu (1998)

6th International Workshop on Project Management and Scheduling (PMS'98)

M Vandenakker (1998)

V

J.-C. Billaut (1998)

in 6th International Workshop on Project Management and Scheduling (PMS’98)

M. VandenAkker (1998)

Three exact methods and an efficient heuristic for solving a bicriteria flowshop scheduling problem

J.-C Billaut (1998)

An approach to solve bicriterion flow-shop scheduling problems

D. Alcaide (1998)

10.1016/S0377-2217(98)00009-5

A bicriteria approach to the two-machine flow shop scheduling problem

S. Sayin (1999)

10.1051/ro:1999108

Les problèmes d'ordonnancement de type flow-shop hybride : état de l'art

A. Vignier (1999)

Les flowshop hybrides : état de l’art

A. Vignier (1999)

Les flowshop hybrides : ´ etat de l'art

A Vignier (1999)

Job and

P. S. Webster (1999)

A multi-criteria heuristic to solve a 2-stage hybrid flowshop scheduling problem

V T 'kindt (2000)

Billaut, L’ordonnancement multicritère

V. T’kindt (2000)

Houngbossa, A multi-criteria heuristic to solve a 2-stage hybrid flowshop scheduling problem

V. T’kindt (2000)

Un algorithme optimal polynomial pour résoudre un problème d ’ ordonnancement bicritère à machines parallèles , in Conference on AutomationComputers EngineeringImageSignal ( AGIS ’ 97 )

J.-C. Billaut (2000)

10.1016/S0377-2217(00)00288-5

Solving a bicriteria scheduling problem on unrelated parallel machines occurring in the glass bottle industry

V. T'Kindt (2001)

10.1016/S0925-5273(00)00039-6

Minimizing total flow time in a two-machine flowshop problem with minimum makespan

J. Gupta (2001)

A multi - criteria heuristic to solve a 2stage hybrid flowshop scheduling problem

J.-C. Billaut

Multiple Criteria Optimization: Classification and Methodology

M Ehrgott Germany

A multi - criteria heuristic to solve a 2 - stage hybrid flowshop scheduling problem

H. Houngbossa

This paper is referenced by

10.3390/SU13031262

Half Open Multi-Depot Heterogeneous Vehicle Routing Problem for Hazardous Materials Transportation

Zhongxin Zhou (2021)

10.1080/00207543.2020.1845914

On the trade-offs between scheduling objectives for unpaced mixed-model assembly lines

Frederik Ferid Ostermeier (2020)

10.1080/00207543.2020.1723815

Service-oriented bi-objective robust collection-disassembly problem with equipment selection

Xin Liu (2020)

10.5772/INTECHOPEN.91169

A Brief Look at Multi-Criteria Problems: Multi-Threshold Optimization versus Pareto-Optimization

N. Vakhania (2020)

10.1109/IESM45758.2019.8948166

Entropy-based bi-objective disassembly line balancing problem

M. Liu (2019)

10.1109/ACCESS.2019.2956059

A New Efficient Algorithm for Hazardous Material Transportation Problem via Lane Reservation

Z. Zhou (2019)

10.1016/J.IFACOL.2019.11.239

Risk level-driven bi-objective stochastic parallel machine scheduling problem

M. Liu (2019)

10.1080/00207543.2018.1504247

Scenario-based heuristic to two-stage stochastic program for the parallel machine ScheLoc problem

M. Liu (2019)

10.3390/EN12101876

A Dual-Objective Substation Energy Consumption Optimization Problem in Subway Systems

H. Liu (2019)

10.1007/978-3-319-95930-6_65

The Hybrid Shuffle Frog Leaping Algorithm Based on Cuckoo Search for Flow Shop Scheduling with the Consideration of Energy Consumption

Ling-Chong Zhong (2018)

10.3390/SU10114257

A Bi-Objective Vehicle-Routing Problem with Soft Time Windows and Multiple Depots to Minimize the Total Energy Consumption and Customer Dissatisfaction

S. Wang (2018)

10.1111/itor.12360

Multiobjective bed management considering emergency and elective patient flows

P. Landa (2018)

10.1007/s10479-018-2775-5

Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic

Emna Dhouib (2018)

10.1016/j.cie.2017.04.026

Bi-criteria single-machine batch scheduling with machine on/off switching under time-of-use tariffs

Junheng Cheng (2017)

10.1016/J.JCLEPRO.2016.07.202

Investment planning and strategic management of sustainable systems for clean power generation: An ε-constraint based multi objective modelling approach

Şebnem Yılmaz Balaman (2016)

10.1109/HPCSim.2016.7568332

Scheduling independent tasks under contiguity constraint: A polyhedral algorithm based-approach for determining and comparing all optimal solutions

H. Salhi (2016)

10.1051/ro/2015063

Bi-objective optimization of single-machine batch scheduling under time-of-use electricity prices

Junheng Cheng (2016)

Complex Job-Shop Scheduling with Batching in Semiconductor Manufacturing

Sebastian Knopp (2016)

10.1080/17517575.2015.1078913

Multiobjective optimisation design for enterprise system operation in the case of scheduling problem with deteriorating jobs

Hongfeng Wang (2016)

Project management under uncertainty: A mixed approach using flexible resource management to exploit schedule flexibility

João Manuel Peixoto Faria (2016)

10.1080/0951192X.2015.1030696

Study of an intelligent and multicriteria scheduling service, using academic benchmarks

F. Ounnar (2016)

Applying a utility based fuzzy probabilistic α-cut method to optimize a constrained multi objective model

Mohammadreza Torkjazi (2015)

10.1016/j.simpat.2015.07.001

Pareto tradeoff scheduling of workflows on federated commercial Clouds

J. J. Durillo (2015)

10.4172/2169-0316.1000147

A Fuzzy Probabilistic Maximum Technique to Optimize an Unconstrained Utility Based Multi Objective Model

Mohammadreza Torkjazi (2015)

10.1515/cait-2015-0025

A Survey of Solving Approaches for Multiple Objective Flexible Job Shop Scheduling Problems

K. Genova (2015)

Parking management system in a dynamic and multi-objective environment. (Système de gestion du stationnement dans un environnement dynamique et multi-objectifs)

Mustapha Ratli (2014)

10.3233/IFS-130958

Optimizing an unconstrained multi objective model using a utility based fuzzy probabilistic α-cut method

M. Torkjazi (2014)

10.1016/J.TRE.2013.12.012

Bi-objective optimization of drayage operations in the service area of intermodal terminals

Kris Braekers (2014)

10.1016/j.ejor.2014.03.026

Fast approximation algorithms for bi-criteria scheduling with machine assignment costs

Kangbok Lee (2014)

10.1155/2014/832814

Model and Method for Multiobjective Time-Dependent Hazardous Material Transportation

Z. Zhou (2014)

10.1109/TPDS.2013.218

Pareto-Optimal Cloud Bursting

M. HoseinyFarahabady (2014)

10.1016/j.ejor.2013.09.017

A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems

Paz Perez-Gonzalez (2014)

See more