Online integrated production-distribution scheduling problems without preemption

被引：4
作者：
Feng, Xin [1 ]
Cheng, Yongxi [1 ]
Zheng, Feifeng [2 ]
Xu, Yinfeng [1 ]
机构：
[1] Xi An Jiao Tong Univ, Sch Management, Xian 710049, Peoples R China
[2] Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200051, Peoples R China
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2016年 / 31卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Supply chain scheduling; Integrated production-distribution problems; Online algorithm; Competitive analysis; DELIVERY; ALGORITHM;
D O I：
10.1007/s10878-015-9841-6
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We study an integrated production-distribution scheduling problem where jobs are released by customers to a manufacturer over time. The jobs are released online, that is, at any time the information of the number, release and processing times of future jobs is unknown, and the processing time of a job becomes known when the job is released. The manufacturer processes the jobs on a single machine. During the processing of jobs preemption is not allowed. Completed jobs are delivered in batches to customers via sufficient capacitated vehicles. For the objective of minimizing the sum of the total delivery time and the total distribution cost, we present a 3-competitive algorithm for the single-customer case and then extend the result to the multi-customer case. A lower bound of two on the competitive ratio of the problem is also given.
引用
收藏
页码：1569 / 1585
页数：17
相关论文
共 21 条
[1]   On-line supply chain scheduling problems with preemption [J].
Averbakh, Igor ;
Xue, Zhihui .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (01) :500-504
[2]   Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem [J].
Averbakh, Igor ;
Baysan, Mehmet .
OPERATIONS RESEARCH LETTERS, 2013, 41 (06) :710-714
[3]   Batching and delivery in semi-online distribution systems [J].
Averbakh, Igor ;
Baysan, Mehmet .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (1-2) :28-42
[4]   Semi-online two-level supply chain scheduling problems [J].
Averbakh, Igor ;
Baysan, Mehmet .
JOURNAL OF SCHEDULING, 2012, 15 (03) :381-390
[5]   On-line integrated production-distribution scheduling problems with capacitated deliveries [J].
Averbakh, Igor .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (02) :377-384
[6]  
Borodin A., 1998, Online Computation and Competitive Analysis
[7]   Integrated Production and Outbound Distribution Scheduling: Review and Extensions [J].
Chen, Zhi-Long .
OPERATIONS RESEARCH, 2010, 58 (01) :130-148
[8]   Integrated scheduling of production and distribution operations [J].
Chen, ZL ;
Vairaktarakis, GL .
MANAGEMENT SCIENCE, 2005, 51 (04) :614-628
[9]   Integrated scheduling of production and delivery on a single machine with availability constraint [J].
Fan, Jing ;
Lu, Xiwen ;
Liu, Peihai .
THEORETICAL COMPUTER SCIENCE, 2015, 562 :581-589
[10]   Integrated batch production and distribution scheduling with limited vehicle capacity [J].
Gao, Su ;
Qi, Lian ;
Lei, Lei .
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2015, 160 :13-25
123