English

运筹学学报 >

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

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

运筹学

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

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

收稿日期: 2015-05-25

  网络出版日期: 2015-09-15

基金资助

上海第二工业大学应用数学重点学科建设项目基金(No. XXKZD1304)

收起

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

摘要

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

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

本文引用格式

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

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].数学的实践与认识, 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
文章导航

/

〈 〉