中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 3: 116 - 122

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.03.014

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

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

Received date: 2015-05-25

  Online published: 2015-09-15

Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.03.014

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.

 
Options
Outlines

/

〈 〉