Multicriteria Scheduling

by T'Kindt, Vincent; Billaut, Jean-Charles; Scott, Henry

• ISBN13: 9783540436171
• ISBN10: 3540436170
• Format: Hardcover
• Copyright: 2002-12-01
• Publisher: Springer Verlag

Summary

First attempt to collect the elementary of multicriteria optimisation theory and the basic models and algorithms of multicriteria scheduling. Composed of numerous illustrations, algorithms and examples which may help the reader in understanding the presented concepts.

Table of Contents

Introduction to scheduling	5	(24)
Definition	5	(1)
Some areas of application	6	(1)
Problems related to production	6	(1)
Other problems	7	(1)
Shop environments	7	(2)
Scheduling problems without assignment	8	(1)
Scheduling and assignment problems with stages	8	(1)
General scheduling and assignment problems	9	(1)
Constraints	9	(3)
Optimality criteria	12	(2)
Minimisation of a maximum function: ``minimax'' criteria	13	(1)
Minimisation of a sum function: ``minisum'' criteria	13	(1)
Typologies and notation of problems	14	(3)
Typologies of problems	14	(2)
Notation of problems	16	(1)
Project scheduling problems	17	(1)
Some fundamental notions	18	(3)
Basic scheduling algorithms	21	(8)
Scheduling rules	21	(1)
Some classical scheduling algorithms	22	(7)
Complexity of problems and algorithms	29	(14)
Complexity of problems	29	(6)
Complexity of algorithms	35	(3)
Application to scheduling	38	(5)
Multicriteria optimisation theory	43	(60)
MCDA and MCDM: the context	43	(2)
MultiCriteria Decision Making	44	(1)
MultiCriteria Decision Aid	44	(1)
Presentation of multicriteria optimisation theory	45	(2)
Definition of optimality	47	(3)
Geometric interpretation using dominance cones	50	(2)
Classes of resolution methods	52	(2)
Determination of Pareto optima	54	(28)
Determination by convex combination of criteria	54	(6)
Determination by parametric analysis	60	(2)
Determination by means of the e-constraint approach	62	(4)
Use of the Tchebycheff metric	66	(3)
Use of the weighted Tchebycheff metric	69	(2)
Use of the augmented weighted Tchebycheff metric	71	(5)
Determination by the goal-attainment approach	76	(5)
Other methods for determining Pareto optima	81	(1)
Multicriteria Linear Programming (MLP)	82	(2)
Initial results	83	(1)
Application of the previous results	83	(1)
Multicriteria Mixed Integer Programming (MMIP)	84	(6)
Initial results	84	(1)
Application of the previous results	85	(2)
Some classical algorithms	87	(3)
The complexity of multicriteria problems	90	(7)
Complexity results related to the solutions	90	(1)
Complexity results related to objective functions	91	(5)
Summary	96	(1)
Interactive methods	97	(1)
Goal programming	98	(5)
Archimedian goal programming	100	(1)
Lexicographical goal programming	101	(1)
Interactive goal programming	101	(1)
Reference goal programming	102	(1)
Multicriteria goal programming	102	(1)
An approach to multicriteria scheduling problems	103	(16)
Justification of the study	103	(4)
Motivations	103	(1)
Some examples	104	(3)
Presentation of the approach	107	(3)
Definitions	107	(2)
Notation of multicriteria scheduling problems	109	(1)
Classes of resolution methods	110	(2)
Application of the process - an example	112	(1)
Some complexity results for multicriteria scheduling problems	113	(6)
Single machine Just-in-Time scheduling problems	119	(28)
Presentation of Just-in-Time (JiT) scheduling problems	119	(1)
Typology of JiT scheduling problems	120	(3)
Definition of the due dates	120	(1)
Definition of the JiT criteria	121	(2)
A new approach for JiT scheduling	123	(2)
Polynomially solvable problems	125	(9)
NP-hard problems	134	(10)
Open problems	144	(3)
Single machine problems	147	(18)
Polynomially solvable problems	147	(9)
Minimisation of K increasing functions of the completion times	147	(1)
Minimisation of the average completion time	147	(3)
Minimisation of the average weighted completion time	150	(1)
Minimisation of crashing time costs	151	(3)
Minimisation of tool changing costs	154	(1)
Minimisation of due date based criteria	155	(1)
NP-hard problems	156	(6)
Minimisation of the average completion time	156	(1)
Minimisation of the average weighted completion time	157	(2)
Minimisation of crashing time costs	159	(3)
Minimisation of tool changing costs	162	(1)
Open problems	162	(3)
Minimisation of the average completion time	162	(1)
Minimisation of crashing time costs	162	(1)
Minimisation of due dates based criteria	163	(2)
Shop problems	165	(52)
Two-machine flowshop problems	165	(1)
The F2|prmu|Lex(Cmax, C) problem	165	(32)
The F2|prmu|Fl(Cmax, C) problem	178	(5)
The F2|prmu, ri|Fl(Cmax, C) problem	183	(1)
The F2|prmu|ε(C / Cmax) problem	184	(5)
The F2|prmu, di|#(Cmax, Tmax) problem	189	(3)
The F2|prmu, di|#(Cmax, U) problem	192	(2)
The F2|prmu, di|#(Cmax, T) problem	194	(3)
m-machine flowshop problems	197	(16)
The F|prmu|Lex(Cmax, C) problem	197	(2)
The F|prmu|#(Cmax, C) problem	199	(5)
The F|prmu, di|ε(Cmax / Tmax) problem	204	(3)
The F|pi,j ε [pi,j; pi,j], prmu|Fl(Cmax, CCw) problem	207	(1)
The F|pi,j = pi ε [pi;pi], prmu|#(Cmax, CCw) problem	208	(3)
The F|prmu, di, nmit|Fl(Ew, Tw) problem	211	(2)
Jobshop and Openshop problems	213	(4)
Jobshop problems	213	(1)
The O2||Lex(Cmax, C) problem	213	(2)
The O3||Lex(Cmax, C) problem	215	(2)
Parallel machines problems	217	(46)
Problems with identical parallel machines	217	(24)
The P2|pmtn, di|ε(Lmax / Cmax) problem	217	(3)
The P3|pmtn, di|ε(Lmax / Cmax) problem	220	(3)
The P2|di|Lex(Tmax, U) problem	223	(2)
The P|di|#(C, U) problem	225	(1)
The P|pmtn|Lex(C, Cmax) problem	226	(1)
The P|di = d non restrictive, nmit|Fl(E, T) problem	227	(3)
The P|di = d unknown, nmit|Fl(E, T) problem	230	(6)
The P|di = d non restrictive, nmit|fmax(Ew, Tw) problem	236	(2)
The P|di = d unknown, pi = p, nmit|Fl(E, T, d) problem	238	(3)
Problems with uniform parallel machines	241	(14)
The Q|pi = p|ε(fmax / Imax) problem	241	(6)
The Q|pi = p|ε(g / fmax) problem	247	(1)
The Q|pmtn|ε(C / Cmax) problem	247	(6)
The Q|di = d unknown, nmit|Fl(E, T) problem	253	(2)
Problems with unrelated parallel machines	255	(8)
The R|pi,j ε [pi,j,pi,j]|Fl(C, CCw) problem	255	(2)
The R|pi,j ε [pi,j;pi,j], di = d unknown|Fl(T, E, CCw) problem	257	(1)
The R|pmtn|ε(Fl(lmax, M) / Cmax) problem	258	(5)
Shop problems with assignment	263	(8)
A hybrid flowshop problem with three stages	263	(1)
Hybrid flowshop problems with k stages	264	(7)
The HFk, (PM(l))kl=1||Fl(Cmax, C) problem	264	(2)
The HFk, (PM(l))kl=1||ε(C / Cmax) problem	266	(1)
The HFk, (PM(l)(t))kl=1|ri(1), di(k)|ε(Cmax / Tmax) problem	266	(5)
A. Notations	271	(6)
Notation of data and variables	271	(1)
Usual notation of single criterion scheduling problems	271	(6)
B. Synthesis on multicriteria scheduling problems	277	(6)
Single machine Just-in-Time scheduling problems	277	(1)
Single machine problems	278	(2)
Shop problems	280	(1)
Parallel machines scheduling problems	281	(1)
Shop scheduling problems with assignment	282	(1)
References	283	(18)
Index	301