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

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

April 2016, 12(2): 757-770. doi: 10.3934/jimo.2016.12.757

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

Ganggang Li ^1, , Xiwen Lu ^1, and Peihai Liu ^1,

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

Received August 2014 Revised March 2015 Published June 2015

Abstract
Related Papers

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: algorithm., Scheduling, availability constraint, delivery.

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

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

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.

show all references

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.

[1]	Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021151
[2]	Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial and Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685
[3]	Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[4]	Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058
[5]	Jian Xiong, Yingwu Chen, Zhongbao Zhou. Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations. Journal of Industrial and Management Optimization, 2016, 12 (2) : 719-737. doi: 10.3934/jimo.2016.12.719
[6]	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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323
[7]	Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044
[8]	Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022066
[9]	Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185
[10]	Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Constraint algorithm for singular field theories in the k-cosymplectic framework. Journal of Geometric Mechanics, 2020, 12 (1) : 1-23. doi: 10.3934/jgm.2020002
[11]	Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022031
[12]	Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[13]	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 and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391
[14]	Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial and Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140
[15]	Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Erratum: Constraint algorithm for singular field theories in the $ k $-cosymplectic framework. Journal of Geometric Mechanics, 2021, 13 (2) : 273-275. doi: 10.3934/jgm.2021007
[16]	Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[17]	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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[18]	Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[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 and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[20]	Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial and Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Ganggang Li Xiwen Lu Peihai Liu
on Google Scholar
Ganggang Li Xiwen Lu Peihai Liu

[Back to Top]