Server scheduling on parallel dedicated machines with fixed job sequences

被引：11

作者：

Cheng, T. C. E. ^{[1
]}

Kravchenko, Svetlana A. ^{[2
]}

Lin, Bertrand M. T. ^{[3
]}

机构：

[1] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Hung Hom, Hong Kong, Peoples R China

[2] Natl Acad Sci Belarus, United Inst Informat Problems, Minsk, BELARUS

[3] Natl Chiao Tung Univ, Inst Informat Management, Hsinchu 300, Taiwan

来源：

NAVAL RESEARCH LOGISTICS | 2019年 / 66卷 / 04期

关键词：

fixed job sequence; makespan; parallel dedicated machines; single server; FLOWSHOP;

D O I：

10.1002/nav.21846

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.

引用

页码：321 / 332

页数：12

共 19 条

[1] Scheduling two parallel machines with a single server: the general case [J].

Abdekhodaee, AH ;

Wirth, A ;

Gan, HS .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (04) :994-1009

[2] Complexity results for parallel machine problems with a single server [J].

Brucker, P ;

Dhaenens-Flipo, C ;

Knust, S ;

Kravchenko, SA ;

Werner, F .

JOURNAL OF SCHEDULING, 2002, 5 (06) :429-457

[3]

Brucker P, 2007, Scheduling Algorithms, DOI [DOI 10.1007/978-3-540-69516-5, 10.1007/978-3-540-69516-5]

[4] Preemptive Parallel-Machine Scheduling with a Common Server to Minimize Makespan [J].

Cheng, T. C. E. ;

Kravchenko, Svetlana A. ;

Lin, Bertrand M. T. .

NAVAL RESEARCH LOGISTICS, 2017, 64 (05) :388-398

[5]

Garey M. R., 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[6]

Glass CA, 2000, NAV RES LOG, V47, P304, DOI 10.1002/(SICI)1520-6750(200006)47:4<304::AID-NAV3>3.0.CO

[7]

2-1

[8] Parallel machine scheduling with a common server [J].

Hall, NG ;

Potts, CN ;

Sriskandarajah, C .

DISCRETE APPLIED MATHEMATICS, 2000, 102 (03) :223-243

[9] Block models for scheduling jobs on two parallel machines with a single server [J].

Hasani, Keramat ;

Kravchenko, Svetlana A. ;

Werner, Frank .

COMPUTERS & OPERATIONS RESEARCH, 2014, 41 :94-97

[10] Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence [J].

Hwang, F. J. ;

Kovalyov, M. Y. ;

Lin, B. M. T. .

ANNALS OF OPERATIONS RESEARCH, 2014, 217 (01) :263-279

← 1 2 →