Heuristics for parallel machine scheduling with batch delivery consideration

Leiyang Wang; Zhaohui Liu

doi:10.3934/jimo.2014.10.259

Article Contents

2014, Volume 10, Issue 1: 259-273. Doi: 10.3934/jimo.2014.10.259

This issue Previous Article A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors Next Article The control parameterization method for nonlinear optimal control: A survey

Heuristics for parallel machine scheduling with batch delivery consideration

Leiyang Wang^1, and
Zhaohui Liu^1,

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

Received: January 31, 2012

Revised: February 28, 2013

Published: December 2013

Abstract Related Papers Cited by

Abstract

We consider the parallel machine scheduling problem in which the finished jobs need to be delivered to a customer in batches by a single vehicle. The goal is to minimize the makespan, i.e., the time by which the vehicle has delivered all jobs and returned to its initial location. We distinguish two types of batching strategies. The strategy of Type 1 permits the jobs processed on different machines to compose a delivery batch, and the strategy of Type 2 assumes that only the jobs processed on the same machine can compose a batch. For both types of the $m$-machine case, we propose $(2-\frac{1}{m})$-approximation algorithms respectively. For both types of the two-machine case, we obtain two improved $\frac{4}{3}$-approximation algorithms.

Keywords:

Mathematics Subject Classification: Primary: 90B35, 90C27; Secondary: 90C59.

Citation:

Related Papers

Cited by

References

[1]	J. H. Ahmadi, R. H. Ahmadi, S. Dasu and C. S. Tang, Batching and scheduling jobs on batch and discrete processors, Operations Research, 40 (1992), 750-763.doi: 10.1287/opre.40.4.750.
[2]	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.
[3]	Z.-L. Chen, Integrated production and outbound distribution scheduling: Review and extensions, Operations Research, 58 (2010), 130-148.doi: 10.1287/opre.1080.0688.
[4]	Z.-L. Chen and G. Pundoor, Order assignment and scheduling in a supply chain, Operations Research, 54 (2006), 555-572.doi: 10.1287/opre.1060.0280.
[5]	Z.-L. Chen and G. Vairaktarakis, Integrated scheduling of production and distribution operations, Management Science, 51 (2005), 614-628.doi: 10.1287/mnsc.1040.0325.
[6]	H. N. Geismar, G. Laporte, L. Lei and C. Sriskandarajah, The integrated production and transportation scheduling problem for a product with a short lifespan, INFORMS Journal on Computing, 20 (2008), 21-33.doi: 10.1287/ijoc.1060.0208.
[7]	H. Gong and L. X. Tang, Scheduling production on parallel machines and batch delivery with limited waiting time constraint, Control and Decision, 26 (2011), 921-924 (in Chinese).
[8]	R. L. Graham, Bounds for certain multiprocessing anomalies, The Bell System Technical Journal, 45 (1966), 1563-1581.doi: 10.1002/j.1538-7305.1966.tb01709.x.
[9]	R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, 17 (1969), 416-429.doi: 10.1137/0117039.
[10]	N. G. Hall and C. N. Potts, The coordination of scheduling and batch deliveries, Annals of Operations Research, 135 (2005), 41-64.doi: 10.1007/s10479-005-6234-8.
[11]	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.
[12]	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.
[13]	C.-S. Su, J. C.-H. Pan and T.-S. Hsu, A new heuristic algorithm for the machine scheduling problem with job delivery coordination, Theoretical Computer Science, 410 (2009), 2581-2591.doi: 10.1016/j.tcs.2009.02.019.
[14]	G. Wang and T. C. E. Cheng, Parallel machine scheduling with batch delivery costs, International Journal of Production Economics, 68 (2000), 177-183.doi: 10.1016/S0925-5273(99)00105-X.
[15]	X. 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.
[16]	W. Y. Zhong, G. Dosa and Z. Y. Tan, On the machine scheduling problem with job delivery coordination, European Journal of Operational Research, 182 (2007), 1057-1072.doi: 10.1016/j.ejor.2006.09.059.