具有多个不可用时间段的单机供应链排序问题

doi:10.15960/j.cnki.issn.1007-6093.2015.03.014

运筹学学报 ›› 2015, Vol. 19 ›› Issue (3): 116-122.doi: 10.15960/j.cnki.issn.1007-6093.2015.03.014

具有多个不可用时间段的单机供应链排序问题

范静^1,*, 张峰¹

1. 上海第二工业大学文理学部, 上海, 201209

收稿日期:2015-05-25 出版日期:2015-09-15 发布日期:2015-09-15
通讯作者: 范静 fanjing@sspu.edu.cn
基金资助:
上海第二工业大学应用数学重点学科建设项目基金(No. XXKZD1304)

Supply chain scheduling problem with multiple unavailability intervals on a single machine

FAN Jing^1,*, ZHANG Feng¹

1. College of Arts and Sciences, Shanghai Second Polytechnic University, Shanghai 201209, China

Received:2015-05-25 Online:2015-09-15 Published:2015-09-15

摘要/Abstract

摘要：

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.

关键词: 不可用时间段, 供应链排序, 强 NP-难, 近似算法

Abstract:

We study a single-machine supply chain scheduling problem with multiple unavailability intervals of equal length. The machine processes jobs in availability intervals and the length of each availability interval is no more than a given constant. The completed jobs are delivered in batches to a customer by one vehicle without capacity restriction. Our objective is to minimize the sum of total delivery time and total delivery cost by scheduling the production and delivery of every job as well as the unavailability intervals. If the interrupted job is resumable, we obtain the optimal schedule in the polynomial time O(n^2). If the interrupted job is non-resumable, we prove that the problem is strongly NP-hard and present a 2-approximation algorithm.

Key words: unavailability interval, supply chain scheduling, strongly NP-hard, approximation algorithm

范静, 张峰. 具有多个不可用时间段的单机供应链排序问题[J]. 运筹学学报, 2015, 19(3): 116-122.

FAN Jing, ZHANG Feng. Supply chain scheduling problem with multiple unavailability intervals on a single machine[J]. Operations Research Transactions, 2015, 19(3): 116-122.

参考文献

陈荣军, 唐国春. 装配系统的供应链排序问题 [J].数学的实践与认识, 2011, 41: 50-56.

Potts C N. Analysis of a heuristic for one machine sequencing with release dates and delivery times [J]. Operations Research, 1980, 28: 1436-1441.

Cheng T C E, Kahlbacher H G. Scheduling with delivery and earliness penalties [J]. Asia Pacific Journal of Operational Research, 1993, 10: 145-152.

Cheng T C E, Gordon V S. Batch delivery scheduling on a single machine [J]. Journal of the Operational Research Society, 1994, 45: 1211-1215.

Cheng T C E, Gordon V S, Kovalyov M Y. Single machine scheduling with batch deliveries [J]. European Journal of Operational Research, 1996, 94: 277-283.

Cheng T C E, Kovalyov M Y, Lin B M T. Single machine scheduling to minimize batch delivery and job earliness penalties [J]. SIAM Journal on Optimization, 1997, 7: 547-559.

Hall N G, Potts C N. Supply chain scheduling: Batching and delivery [J]. Operations Research, 2003, 51: 566-584.

Chen Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations [J]. Management Science, 2005, 51: 614-628.

Hall N G, Potts C N. The coordination of scheduling and batch deliveries [J]. Annals of Operations Research}, 2005, 135: 41-64.

Li K P, Ganesan V K, Sivakumar A I. Synchronized scheduling of assembly and multi-destination air-transportation in a consumer electronics supply chain [J]. International Journal of Production Research, 2005, 43: 2671-2685.

Lee C Y, Chen Z L. Machine scheduling with transportation considerations [J]. Journal of Scheduling, 2001, 4: 3-24.

Chen W. Minimizing total flow time in the single-machine scheduling problem with periodic maintenance [J]. Journal of Operations Research Society, 2006, 57: 410-415.

Fan J, Lu X W. Supply chain scheduling problem in the hospital with periodic working time on a single machine [J]. Journal of Combinatorial Optimization, Doi: 10.1007/s10878-015-9857-y.

Qi X, Chen T, Tu F. Scheduling the maintenance on a single machine [J]. Journal of Operations Research Society, 1999, 50: 1071-1078.

Akturk M, Ghosh J, Gunes E. Scheduling with tool changes to minimize total completion time: A study of heuristics and their performance [J]. Naval Research Logistics, 2003, 50: 15-30.

Akturk M, Ghosh J, Gunes E. Scheduling with tool changes to minimize total completion time: Basic results and SPT performance [J]. European Journal of Operational Research, 2004, 157: 784-790.

Qi X. A note on worst-case performance of heuristics for maintenance scheduling problems [J]. Discrete Applied Mathematics, 2007, 155: 416-422.

Chen Z L. Integrated production and outbound distribution scheduling: review and extensions [J]. Operations Research, 2010, 58: 130-148.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[6]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[7]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[8]	张龙. 储存时间有上限的两阶段供应链排序问题[J]. 运筹学学报, 2017, 21(2): 126-134.
[9]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[10]	张玉忠, 张龙. 优化交货期窗口的两阶段供应链排序问题[J]. 运筹学学报, 2016, 20(4): 30-38.
[11]	范静, 鲁习文. 机器带不可用时间限制的简单线性恶化供应链排序问题[J]. 运筹学学报, 2016, 20(4): 69-76.
[12]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[13]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[14]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[15]	刘颖, 张新功. 具有学习效应的三层供应链排序问题[J]. 运筹学学报, 2016, 20(1): 31-42.

具有多个不可用时间段的单机供应链排序问题

Supply chain scheduling problem with multiple unavailability intervals on a single machine

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价