Coordinated scheduling on parallel, machines with batch delivery

被引：18

作者：

Wan, Long ^{[1
]}

Zhang, An ^{[2
]}

机构：

[1] Jiangxi Univ Finance & Econ, Sch Informat Technol, Nanchang, Jiangxi, Peoples R China

[2] Hangzhou Dianzi Univ, Inst Operat Res & Cybernet, Hangzhou 310018, Zhejiang, Peoples R China

来源：

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 2014年 / 150卷

基金：

中国国家自然科学基金;

关键词：

Scheduling; Batching and delivery; Complexity; Worst-case analysis; COMMON DUE-DATE; SINGLE-MACHINE; EARLINESS-TARDINESS; COSTS;

D O I：

10.1016/j.ijpe.2014.01.009

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper considers coordinated scheduling on parallel identical machines with batch delivery. Jobs are first processed on m parallel and identical machines in the manufacturing facility and then delivered to the customer in batches. There are v identical transporters that can carry up to c jobs in one shipment. The objective is to minimize the sum of job arrival times. We show that the problem is NP-hard in the strong sense if m is part of the input. Besides, we propose the first approximation algorithm for the problem and prove that the worst case ratio of the algorithm is 2-1/m for any m. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：199 / 203

页数：5

共 14 条

[1] Machine scheduling with job delivery coordination
Chang, YC
Lee, CY
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 158 (02) : 470 - 487
[2] Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs
Chen, ZL
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 93 (01) : 49 - 60
[3] Gong H, 2008, LECT NOTES COMPUT SC, V5092, P670
[4] The coordination of scheduling and batch deliveries
Hall, NG
Potts, CN
[J]. ANNALS OF OPERATIONS RESEARCH, 2005, 135 (01) : 41 - 64
[5] Supply chain scheduling: Batching and delivery
Hall, NG
Potts, CN
[J]. OPERATIONS RESEARCH, 2003, 51 (04) : 566 - 584
[6] Improved algorithms for two single machine scheduling problems
He, Yong
Zhong, Weiya
Gu, Huikun
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 363 (03) : 257 - 265
[7] Batch delivery scheduling with batch delivery cost on a single machine
Ji, Min
He, Yong
Cheng, T. C. E.
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 176 (02) : 745 - 755
[8] Lee CY, 2001, J SCHED, V4, P3, DOI 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO
[9] 2-D
[10] Supply chain scheduling at the manufacturer to minimize inventory holding and delivery costs
Selvarajah, Esaignani
Zhang, Rui
[J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2014, 147 : 117 - 124

← 1 2 →