# American Institute of Mathematical Sciences

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

## 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, 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.
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1002/nav.20175. Google Scholar
 [1] 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 [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] 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 [4] 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 [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] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 [13] Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007 [14] 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, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [15] 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, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088 [16] Kathryn Haymaker, Beth Malmskog, Gretchen L. Matthews. Locally recoverable codes with availability t≥2 from fiber products of curves. Advances in Mathematics of Communications, 2018, 12 (2) : 317-336. doi: 10.3934/amc.2018020 [17] Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437 [18] 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 [19] Mario Grassi, Giuseppe Pontrelli, Luciano Teresi, Gabriele Grassi, Lorenzo Comel, Alessio Ferluga, Luigi Galasso. Novel design of drug delivery in stented arteries: A numerical comparative study. Mathematical Biosciences & Engineering, 2009, 6 (3) : 493-508. doi: 10.3934/mbe.2009.6.493 [20] Shalela Mohd Mahali, Song Wang, Xia Lou. Determination of effective diffusion coefficients of drug delivery devices by a state observer approach. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1119-1136. doi: 10.3934/dcdsb.2011.16.1119

2018 Impact Factor: 1.025

## Metrics

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

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]