Parallel machine problems with equal processing times: a survey

被引：45
作者：
Kravchenko, Svetlana A. [2 ]
Werner, Frank [1 ]
机构：
[1] Univ Magdeburg, Fak Math, D-39106 Magdeburg, Germany
[2] United Inst Informat Problems, Minsk 220012, BELARUS
来源：
JOURNAL OF SCHEDULING | 2011年 / 14卷 / 05期
关键词：
Parallel machine problem; Equal processing times; Non-preemptive problems; Preemptive problems; Polynomial algorithms; NP-hard problems; UNIT-LENGTH JOBS; SCHEDULING PROBLEMS; COMPLEXITY; ALGORITHM; RELEASE; NUMBER;
D O I：
10.1007/s10951-011-0231-3
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. All jobs have to be processed on a set of parallel machines. Preemptions can be either allowed or forbidden. The aim is to construct a feasible schedule such that a given criterion is minimized. In this paper, we survey existing approaches for the problem class considered.
引用
收藏
页码：435 / 444
页数：10
相关论文
共 46 条
  • [1] [Anonymous], 1983, Mathematical Programming The State of the Art, DOI DOI 10.1007/978-3-642-68874-4_9
  • [2] Baptiste P., 1999, Journal of Scheduling, V2, P245, DOI 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO
  • [3] 2-5
  • [4] Scheduling equal-length jobs on identical parallel machines
    Baptiste, P
    [J]. DISCRETE APPLIED MATHEMATICS, 2000, 103 (1-3) : 21 - 32
  • [5] Preemptive scheduling of equal-length jobs to maximize weighted throughput
    Baptiste, P
    Chrobak, M
    Dürr, C
    Jawor, W
    Vakhania, N
    [J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (03) : 258 - 264
  • [6] Baptiste P, 2004, 4OR-Q J OPER RES, V2, P111
  • [7] Baptiste P., 2004, HDB SCHEDULING ALGOR, P78
  • [8] The complexity of mean flow time scheduling problems with release times
    Baptiste, Philippe
    Brucker, Peter
    Chrobak, Marek
    Durr, Christoph
    Kravchenko, Svetlana A.
    Sourd, Francis
    [J]. JOURNAL OF SCHEDULING, 2007, 10 (02) : 139 - 146
  • [9] Brucker P., 1977, Mathematics of Operations Research, V2, P275, DOI 10.1287/moor.2.3.275
  • [10] BRUCKER P, 2010, COMPLEXITY RESULTS S
12345