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

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

Abstract

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

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.

References

陈荣军, 唐国春. 装配系统的供应链排序问题 [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]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[3]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[4]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[5]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[6]	WANG Yishui, XU Dachuan, WU Chenchen. A semidefinite programming rounding algorithm for correlation clustering problem [J]. Operations Research Transactions, 2018, 22(1): 67-76.
[7]	ZHANG Long. Two-stage supply chain scheduling with a limited holding time [J]. Operations Research Transactions, 2017, 21(2): 126-134.
[8]	CHEN Guangting, CHEN Lei, ZHANG An, CHEN Yong. Approximation algorithms for two-machine flow shop scheduling with an outsourcing option [J]. Operations Research Transactions, 2016, 20(4): 109-114.
[9]	ZHANG Yuzhong, ZHANG Long. Two-stage supply chain scheduling with an assignable common due window [J]. Operations Research Transactions, 2016, 20(4): 30-38.
[10]	FAN Jing, LU Xiwen. Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint [J]. Operations Research Transactions, 2016, 20(4): 69-76.
[11]	ZHONG Weiya, MA Xiaoru. A no-wait flowshop scheduling problem with processing flexibility and transportation [J]. Operations Research Transactions, 2016, 20(4): 93-101.
[12]	SUN Ting, LI Gaidi, XU Wenqing. Approximation algorithms for max cut and max bisection problems using semi-definite programming relaxations [J]. Operations Research Transactions, 2016, 20(3): 21-32.
[13]	FANG Rui, LUO Wenchang. Approximation algorithm for the fault-tolerant facility placement problem with penalties [J]. Operations Research Transactions, 2016, 20(2): 69-78.
[14]	LIU Ying, ZHANG Xingong. Three-echelon supply chain scheduling problem with learning effect [J]. Operations Research Transactions, 2016, 20(1): 31-42.
[15]	YAN Lincheng,XIAO Han,ZHAO Hongjuan,SUN Xiaoqi. An approximation algorithm for reliable facility location problem [J]. Operations Research Transactions, 2015, 19(4): 14-24.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments