The coordination of single-machine scheduling with availability constraints and delivery

Ganggang Li; Xiwen Lu; Peihai  Liu

doi:10.3934/jimo.2016.12.757

Article Contents

2016, Volume 12, Issue 2: 757-770. Doi: 10.3934/jimo.2016.12.757

This issue Previous Article A polynomial-time interior-point method for circular cone programming based on kernel functions Next Article Approximate algorithms for unrelated machine scheduling to minimize makespan

The coordination of single-machine scheduling with availability constraints and delivery

1.
Department of Mathematics, School of Science, East China University of Science and Technology, Shanghai 200237

Received: July 31, 2014

Revised: February 28, 2015

Published: March 2016

Abstract Related Papers Cited by

Abstract

Single-machine scheduling problems with production and delivery are studied in this paper. There is only one delivery vehicle with capacity $z$. Jobs are not allowed to resume. The $P \rightarrow D$ system and $D \rightarrow P$ system are considered, respectively. For the machine with an availability constraint, we present two $4/3$-approximation algorithms and show that the bounds are tight. For the machine with periodic availability constraints, we provide two polynomial time approximation algorithms which are the best possible.

Keywords:

Mathematics Subject Classification: Primary: 90B35, 90C27.

Citation:

Related Papers

Cited by

References

[1]	Y. C. Chang and C. Y. Lee, Machine scheduling with job delivery coordination, European Journal of Operational Research, 158 (2004), 470-487.doi: 10.1016/S0377-2217(03)00364-3.
[2]	N. G. Hall and C. N. Potts, Supply chain scheduling: Batching and delivery, Operations Research, 51 (2003), 566-584.doi: 10.1287/opre.51.4.566.16106.
[3]	M. Ji, Y. He and T. C. E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan, Computers & Operations Research, 34 (2007), 1764-1770.doi: 10.1016/j.cor.2005.05.034.
[4]	C. Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization, 9 (1996), 395-416.doi: 10.1007/BF00121681.
[5]	C. Y. Lee and Z. L. Chen, Machine scheduling with transportation considerations, Journal of Scheduling, 4 (2001), 3-24.doi: 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D.
[6]	C. Y. Lee, L. Lei and M. Pinedo, Current trends in deterministic scheduling, Annals of Operations Research, 70 (1997), 1-41.doi: 10.1023/A:1018909801944.
[7]	C. L. Li and J. W. Ou, Machine scheduling with pickup and delivery, Naval Research Logistics, 52 (2005), 617-630.doi: 10.1002/nav.20101.
[8]	C. L. Li, G. Vairaktarakis and C. Y. Lee, Machine scheduling with deliveries to multiple customer locations, European Journal of Operational Research, 164 (2005), 39-51.doi: 10.1016/j.ejor.2003.11.022.
[9]	G. Schmidt, Scheduling with limited machine availability, European Journal of Operational Research, 121 (2000), 1-15.doi: 10.1016/S0377-2217(98)00367-1.
[10]	L. X. Tang, J. Guan and G. F. Hu, Steelmaking and refining coordinated scheduling problem with waiting time and transportation consideration, Computers & Industrial Engineering, 58 (2010), 239-248.doi: 10.1016/j.cie.2009.07.014.
[11]	D. J. Thomas and P. M. Griffin, Coordinated supply chain management, European Journal of Operational Research, 94 (1996), 1-15.doi: 10.1016/0377-2217(96)00098-7.
[12]	L. Y. Wang and Z. H. Liu, Heuristics for parallel machine scheduling with batch delivery consideration, Journal of Industrial and Management Optimization, 10 (2014), 259-273.doi: 10.3934/jimo.2014.10.259.
[13]	X. L. Wang and T. C. E. Cheng, Machine scheduling with an availability constraint and job delivery coordination, Naval Research Logistics, 54 (2007), 11-20.doi: 10.1002/nav.20175.