The coupled unit-time operations problem on identical parallel machines with respect to the makespan

被引：0
作者：
Munier-Kordon, Alix [1 ]
Rebaine, Djamal [2 ]
机构：
[1] Univ Paris 06, Dept SOC, Lab LIP6, F-75252 Paris 05, France
[2] Univ Quebec Chicoutimi, Dept Informat & Math, Chicoutimi, PQ G7H 2B1, Canada
来源：
OPERATIONS RESEARCH LETTERS | 2014年 / 42卷 / 01期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Coupled operations; Makespan; Special case; Time delays; Worst-case analysis; TASKS;
D O I：
10.1016/j.orl.2013.11.006
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper addresses the problem of scheduling n unit-time coupled operations on m identical parallel machines with minimum time delay considerations so as to minimize the overall completion time, known as the makespan. Two approximation algorithms, along with their worst-case analysis, are presented. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：21 / 26
页数：6
相关论文
共 11 条
  • [1] AHR D, 2004, MATH METHOD OPER RES, V59, P93
  • [2] [Anonymous], NAVAL RES LOGIST Q
  • [3] A note on scheduling identical coupled tasks in logarithmic time
    Baptiste, Philippe
    [J]. DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) : 583 - 587
  • [4] Scheduling of coupled tasks with unit processing times
    Blazewicz, J.
    Ecker, K.
    Kis, T.
    Potts, C. N.
    Tanas, M.
    Whitehead, J.
    [J]. JOURNAL OF SCHEDULING, 2010, 13 (05) : 453 - 461
  • [5] Scheduling of coupled tasks and one-machine no-wait robotic cells
    Brauner, Nadia
    Finke, Gerd
    Lehoux-Lebacque, Vassilissa
    Potts, Chris
    Whitehead, Jonathan
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) : 301 - 307
  • [6] Complexity results for single-machine problems with positive finish-start time-lags
    Brucker, P
    Knust, S
    [J]. COMPUTING, 1999, 63 (04) : 299 - 316
  • [7] Gupta J.N.D., 1994, PREPRINT
  • [8] Scheduling for a multifunction phased array radar system
    Orman, AJ
    Potts, CN
    Shahani, AK
    Moore, AR
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (01) : 13 - 25
  • [9] Heuristics for a coupled-operation scheduling problem
    Potts, C. N.
    Whitehead, J. D.
    [J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2007, 58 (10) : 1375 - 1388
  • [10] Simonin G., 2010, ELECT NOTES DISCRETE, V36, P647
12