Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint

Expand
  • 1. College of Arts and Sciences, Shanghai Polytechnic University, Shanghai 201209, China; 2. School of Science, East China University of Science and Technology, Shanghai 200237, China

Received date: 2016-02-01

  Online published: 2016-12-15

Abstract

We study a single-machine supply chain scheduling problem with one unavailability constraint, in which the actual processing time of a job depends on the deteriorating operator and the beginning time of processing and the interrupted job is non-resumable. The sufficient available vehicles without capacity limit deliver batches of completed jobs to the customer. And the completed jobs before the unavailability interval must be delivered before or by the start time of the unavailability interval. The objective is to minimize the sum of total delivery time and total delivery cost. We show that the problem is NP-hard, and present a pseudo-polynomial-time dynamic programming. Moreover, we achieve a full polynomial time approximation scheme (FPTAS) based on the lower bound and the upper bound of the objective function value of the problem.

Cite this article

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

References

[1] Browne S, Yechiali U. Scheduling deterioration jobs on a single processor [J]. Operations Research, 1990, 38: 495-498.
[2] Gupta N D, Gupta K.  Single facility scheduling with nonlinear processing [J]. Computer and Industrial Engineering, 1988, 14: 387-393.
[3] Mosheiov G.  V-shaped policies for scheduling deteriorating jobs [J]. Operations Research,  1991, 39: 979-991.
[4] Mosheiov G.  Scheduling jobs under simple linear deterioration [J]. Computers and Operations Research, 1994, 21: 653-659.
[5] Wu C C, Lee W C. Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine [J]. Information Processing Letters, 2003, 87: 89-93.
[6] Ji M, He Y, Cheng T C E.  Scheduling linear deteriorating jobs with an availability constraint on a single machine [J]. Theoretical Computer Science, 2006, 362: 115-126.
[7] 马英, 左春荣, 杨善林. 带不可用时间段和恶化加工时间的单机调度 [J]. 系统工程学报, 2010, 25: 371-378.
[8] 党蕊, 赵玉芳. 带有可变加工时间和可用性限制的排序问题 [J]. 沈阳师范大学学报(自然科学版), 2015, 33: 28-32.
[9] Wang X,  Cheng T C E.  Machine scheduling with an availability constraint and job delivery coordination [J].  Naval Research Logistics, 2007, 54: 11-20.
[10] Yuan J J,  Shi L,  Ou J W.  Single machine scheduling with forbidden intervals and job delivery times [J].  Asia Pacific Journal of Operational Research, 2008, 25: 317-325.
[11] Kacem I.  Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed nonavailability interval [J].  Journal of Combinatorial Optimization, 2009, 17: 117-133.
[12] Yin Y, Ye D, Zhang G.  Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval [J]. Information Sciences, 2014, 274: 310-322.
[13] Fan J, Lu X W, Liu P H. Integrated scheduling of production and delivery on a single machine with availability constraint [J]. Theoretical Computer Science, 2015, 562: 581-589.
 
Outlines

/