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]

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, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019122

[17]

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

[18]

Takeshi Fukao. Variational inequality for the Stokes equations with constraint. Conference Publications, 2011, 2011 (Special) : 437-446. doi: 10.3934/proc.2011.2011.437

[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 (14)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]