Online citations, reference lists, and bibliographies.
← Back to Search

Multicriteria Scheduling Problems: A Survey

V. T'kindt, J. Billaut
Published 2001 · Computer Science

Save to my Library
Download PDF
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.
Get Citationsy
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
Semantic Scholar Logo Some data provided by SemanticScholar