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 [J].

Baptiste, Philippe .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) :583-587

[4] Scheduling of coupled tasks with unit processing times [J].

Blazewicz, J. ;

Ecker, K. ;

Kis, T. ;

Potts, C. N. ;

Tanas, M. ;

Whitehead, J. .

JOURNAL OF SCHEDULING, 2010, 13 (05) :453-461

[5] Scheduling of coupled tasks and one-machine no-wait robotic cells [J].

Brauner, Nadia ;

Finke, Gerd ;

Lehoux-Lebacque, Vassilissa ;

Potts, Chris ;

Whitehead, Jonathan .

COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (02) :301-307

[6] Complexity results for single-machine problems with positive finish-start time-lags [J].

Brucker, P ;

Knust, S .

COMPUTING, 1999, 63 (04) :299-316

[7]

Gupta J.N.D., 1994, PREPRINT

[8] Scheduling for a multifunction phased array radar system [J].

Orman, AJ ;

Potts, CN ;

Shahani, AK ;

Moore, AR .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (01) :13-25

[9] Heuristics for a coupled-operation scheduling problem [J].

Potts, C. N. ;

Whitehead, J. D. .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2007, 58 (10) :1375-1388

[10]

Simonin G., 2010, ELECT NOTES DISCRETE, V36, P647

← 1 2 →