文献类型：期刊文献

英文题名：On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost

作者：Han, Bin[1,2];Zhang, Wenjun[1,2];Lu, Xiwen[1];Lin, Yingzi[3]

机构：[1]E China Univ Sci & Technol, Complex & Intelligent Syst Ctr, Shanghai 200237, Peoples R China;[2]Univ Saskatchewan, Dept Mech Engn, Saskatoon, SK S7N 5A9, Canada;[3]Northeastern Univ, Dept Mech & Ind Engn, Boston, MA 02115 USA

年份：2015

卷号：244

期号：3

起止页码：704

外文期刊名：EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

收录：;EI(收录号：20150900575238);WOS:【SCI-EXPANDED(收录号:WOS:000353737900003)】；

基金：We acknowledge partial financial support of this research by Fundamental Research Funds for the Control Faculty of the East China University of Science & Technology.

语种：英文

外文关键词：Supply chain scheduling; On-line algorithm; Delivery cost; Makespan

摘要：This paper investigates minimization of both the makespan and delivery costs in on-line supply chain scheduling for single-machine and parallel-machine configurations in a transportation system with a single customer. The jobs are released as they arrive, which implies that no information on upcoming jobs, such as the release time, processing time, and quantity, is known beforehand to the scheduler. The jobs are processed on one machine or parallel machines and delivered to the customer. The primary objective of the scheduling is time, which is makespan in this case. The delivery cost, which changes due to the varying number of batches (though the cost for each batch is assumed to be the same) in delivery, is also concerned. The goal of scheduling is thus to minimize both the makespan and the total delivery cost This scheduling involves deciding when to process jobs, which machine to process jobs, when to deliver jobs, and which batch to include jobs. We define 10 problems in terms of (1) the machine configuration, (2) preemption of job processing, (3) the number of vehicles, and (4) the capacity of vehicles. These problems (P1, P2,..., P10) have never been studied before in literature. The lower bound for each problem is first proved by constructing a series of intractable instances. Algorithms for these problems, denoted by H1, H2,..., H10, respectively, are then designed and a theoretical analysis is performed. The results show that H1, H2, H6, and H7 are optimal ones according to the competitive ratio criterion, while the other algorithms deviate slightly from the optimum. We also design the optimal algorithm for a special case of P5. A case study is provided to illustrate the performance of H5 and to demonstrate the practicality of the algorithms. (C) 2015 Elsevier B.V. All rights reserved.