Scheduling with limited machine availability

被引：374
作者：
Schmidt, G [1 ]
机构：
[1] Univ Saarlandes, Fachbereich Wirtschaftswissensch, Lehrstuhl Informat & Technol Management, D-66041 Saarbrucken, Germany
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2000年 / 121卷 / 01期
关键词：
scheduling theory; availability constraints; algorithms;
D O I：
10.1016/S0377-2217(98)00367-1
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper reviews results related to deterministic scheduling problems where machines are not continuously available for processing. There might be incomplete information about the points of time machines change availability. The complexity of single and multi machine problems is analyzed considering criteria on completion times and due dates. The review mainly covers intractability results, polynomial optimization and approximation algorithms. Tn some places too results from enumerative algorithms and heuristics are surveyed. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：1 / 15
页数：15
相关论文
共 45 条
[1]   SINGLE-MACHINE FLOW-TIME SCHEDULING WITH A SINGLE BREAKDOWN [J].
ADIRI, I ;
BRUNO, J ;
FROSTIG, E ;
KAN, AHGR .
ACTA INFORMATICA, 1989, 26 (07) :679-685
[2]  
ALBERS S, 1998, MPII981021 M PLANCK
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
BLAZEWICZ J, 1998, B9802 U SAARL FACHB
[5]  
BLAZEWICZ J, 1997, NOTE PARALLEL BRANCH
[6]  
BLAZEWICZ J, 1996, SCHEDULING COMPUTER
[7]  
BLAZEWICZ J, UNPUB SCHEDULING PRE
[8]   A LOWER-BOUND FOR RANDOMIZED ONLINE SCHEDULING ALGORITHMS [J].
CHEN, B ;
VANVLIET, A ;
WOEGINGER, GJ .
INFORMATION PROCESSING LETTERS, 1994, 51 (05) :219-222
[9]   SCHEDULING FLAT GRAPHS [J].
DOLEV, D ;
WARMUTH, M .
SIAM JOURNAL ON COMPUTING, 1985, 14 (03) :638-657
[10]   PROFILE SCHEDULING OF OPPOSING FORESTS AND LEVEL ORDERS [J].
DOLEV, D ;
WARMUTH, MK .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (04) :665-687
12345