• Previous Article
    A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors
  • JIMO Home
  • This Issue
  • Next Article
    The control parameterization method for nonlinear optimal control: A survey
January  2014, 10(1): 259-273. doi: 10.3934/jimo.2014.10.259

Heuristics for parallel machine scheduling with batch delivery consideration

1. 

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

Received  February 2012 Revised  March 2013 Published  October 2013

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.
Citation: Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
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. doi: 10.1287/opre.40.4.750. Google Scholar

[2]

Y.-C. Chang and C.-Y. Lee, Machine scheduling with job delivery coordination,, European Journal of Operational Research, 158 (2004), 470. doi: 10.1016/S0377-2217(03)00364-3. Google Scholar

[3]

Z.-L. Chen, Integrated production and outbound distribution scheduling: Review and extensions,, Operations Research, 58 (2010), 130. doi: 10.1287/opre.1080.0688. Google Scholar

[4]

Z.-L. Chen and G. Pundoor, Order assignment and scheduling in a supply chain,, Operations Research, 54 (2006), 555. doi: 10.1287/opre.1060.0280. Google Scholar

[5]

Z.-L. Chen and G. Vairaktarakis, Integrated scheduling of production and distribution operations,, Management Science, 51 (2005), 614. doi: 10.1287/mnsc.1040.0325. Google Scholar

[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. doi: 10.1287/ijoc.1060.0208. Google Scholar

[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. Google Scholar

[8]

R. L. Graham, Bounds for certain multiprocessing anomalies,, The Bell System Technical Journal, 45 (1966), 1563. doi: 10.1002/j.1538-7305.1966.tb01709.x. Google Scholar

[9]

R. L. Graham, Bounds on multiprocessing timing anomalies,, SIAM Journal on Applied Mathematics, 17 (1969), 416. doi: 10.1137/0117039. Google Scholar

[10]

N. G. Hall and C. N. Potts, The coordination of scheduling and batch deliveries,, Annals of Operations Research, 135 (2005), 41. doi: 10.1007/s10479-005-6234-8. Google Scholar

[11]

C.-Y. Lee and Z.-L. Chen, Machine scheduling with transportation considerations,, Journal of Scheduling, 4 (2001), 3. doi: 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D. Google Scholar

[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. doi: 10.1016/j.ejor.2003.11.022. Google Scholar

[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. doi: 10.1016/j.tcs.2009.02.019. Google Scholar

[14]

G. Wang and T. C. E. Cheng, Parallel machine scheduling with batch delivery costs,, International Journal of Production Economics, 68 (2000), 177. doi: 10.1016/S0925-5273(99)00105-X. Google Scholar

[15]

X. Wang and T. C. E. Cheng, Machine scheduling with an availability constraint and job delivery coordination,, Naval Research Logistics, 54 (2007), 11. doi: 10.1002/nav.20175. Google Scholar

[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. doi: 10.1016/j.ejor.2006.09.059. Google Scholar

show all references

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. doi: 10.1287/opre.40.4.750. Google Scholar

[2]

Y.-C. Chang and C.-Y. Lee, Machine scheduling with job delivery coordination,, European Journal of Operational Research, 158 (2004), 470. doi: 10.1016/S0377-2217(03)00364-3. Google Scholar

[3]

Z.-L. Chen, Integrated production and outbound distribution scheduling: Review and extensions,, Operations Research, 58 (2010), 130. doi: 10.1287/opre.1080.0688. Google Scholar

[4]

Z.-L. Chen and G. Pundoor, Order assignment and scheduling in a supply chain,, Operations Research, 54 (2006), 555. doi: 10.1287/opre.1060.0280. Google Scholar

[5]

Z.-L. Chen and G. Vairaktarakis, Integrated scheduling of production and distribution operations,, Management Science, 51 (2005), 614. doi: 10.1287/mnsc.1040.0325. Google Scholar

[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. doi: 10.1287/ijoc.1060.0208. Google Scholar

[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. Google Scholar

[8]

R. L. Graham, Bounds for certain multiprocessing anomalies,, The Bell System Technical Journal, 45 (1966), 1563. doi: 10.1002/j.1538-7305.1966.tb01709.x. Google Scholar

[9]

R. L. Graham, Bounds on multiprocessing timing anomalies,, SIAM Journal on Applied Mathematics, 17 (1969), 416. doi: 10.1137/0117039. Google Scholar

[10]

N. G. Hall and C. N. Potts, The coordination of scheduling and batch deliveries,, Annals of Operations Research, 135 (2005), 41. doi: 10.1007/s10479-005-6234-8. Google Scholar

[11]

C.-Y. Lee and Z.-L. Chen, Machine scheduling with transportation considerations,, Journal of Scheduling, 4 (2001), 3. doi: 10.1002/1099-1425(200101/02)4:1<3::AID-JOS57>3.0.CO;2-D. Google Scholar

[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. doi: 10.1016/j.ejor.2003.11.022. Google Scholar

[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. doi: 10.1016/j.tcs.2009.02.019. Google Scholar

[14]

G. Wang and T. C. E. Cheng, Parallel machine scheduling with batch delivery costs,, International Journal of Production Economics, 68 (2000), 177. doi: 10.1016/S0925-5273(99)00105-X. Google Scholar

[15]

X. Wang and T. C. E. Cheng, Machine scheduling with an availability constraint and job delivery coordination,, Naval Research Logistics, 54 (2007), 11. doi: 10.1002/nav.20175. Google Scholar

[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. doi: 10.1016/j.ejor.2006.09.059. Google Scholar

[1]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[2]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685

[3]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[4]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271

[5]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[6]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[7]

Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007

[8]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[9]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749

[10]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353

[11]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[12]

Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial & Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811

[13]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008

[14]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[15]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429

[16]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

[17]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521

[18]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[19]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[20]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]