文献类型：期刊文献

英文题名：Integrated scheduling of production and delivery on a single machine with availability constraint

作者：Fan, Jing[1,2];Lu, Xiwen[1];Liu, Peihai[1]

机构：[1]E China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China;[2]Shanghai Second Polytech Univ, Sch Sci, Shanghai 201209, Peoples R China

年份：2015

卷号：562

期号：C

起止页码：581

外文期刊名：THEORETICAL COMPUTER SCIENCE

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

基金：Research supported by the National Natural Science Foundation of China (Nos. 11371137, 11101147) and the key discipline 'Applied Mathematics' of Shanghai Second Polytechnic University (Nos. A30XK1408004, XXKZD1304).

语种：英文

外文关键词：Integrated scheduling; Availability constraint; Delivery cost; Algorithm; PTAS

摘要：We study the problem of integrated scheduling of production and delivery on a single machine. Because of the availability constraint of the machine, jobs in processing may be interrupted. When the machine becomes available again, the job interrupted can resume or restart processing. The completed jobs are delivered in batches to one customer by vehicles without capacity constraint. The goal is to minimize the sum of total delivery time and total delivery cost. If the interrupted job is resumable, we provide an optimal algorithm with polynomial time. If the interrupted job is non-resumable, we propose an algorithm with the worst-case performance ratio 3/2. Moreover, we show that the problem has a polynomial time approximation scheme (PTAS). (C) 2014 Elsevier B.V. All rights reserved.