American Institute of Mathematical Sciences

Advanced
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

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

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

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

[4]

C. Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization, 9 (1996), 395-416. doi: 10.1007/BF00121681.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

[4]

C. Y. Lee, Machine scheduling with an availability constraint, Journal of Global Optimization, 9 (1996), 395-416. doi: 10.1007/BF00121681.  Google Scholar

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

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

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

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

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

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

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

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

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

[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 & Management Optimization, 2021  doi: 10.3934/jimo.2021151
[2]

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
[3]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685
[4]

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
[5]

Jian Xiong, Yingwu Chen, Zhongbao Zhou. Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations. Journal of Industrial & 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 & 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 & Management Optimization, 2021  doi: 10.3934/jimo.2021044
[8]

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
[9]

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
[10]

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 & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[11]

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
[12]

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2022, 18 (1) : 1-24. doi: 10.3934/jimo.2020140
[13]

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
[14]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[15]

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
[16]

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 & Management Optimization, 2020, 16 (6) : 2943-2969. doi: 10.3934/jimo.2019088
[17]

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
[18]

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 & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817
[19]

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
[20]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy