April  2015, 11(2): 685-700. doi: 10.3934/jimo.2015.11.685

Two-machine scheduling with periodic availability constraints to minimize makespan

1. 

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

Received  November 2013 Revised  May 2014 Published  September 2014

A two-machine scheduling problem where one machine has periodic availability constraints has been studied. The objective is to minimize makepan. For the nonresumable version, we give a better approximation algorithm with performance ratio of $4/3$. For the resumable version, we provide an offline $4/3$-approximation algorithm and an optimal online algorithm, respectively.
Citation: 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
References:
[1]

T. C. E. Cheng and G. Wang, An improved heuristic for two-machine flowshop scheduling with an availability constraint, Operation Research Letters, 26 (2000), 223-229. doi: 10.1016/S0167-6377(00)00033-X.

[2]

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

[3]

M. Ji, Y. He and T. C. E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan, Computer & Operations Research, 34 (2007), 1764-1770. doi: 10.1016/j.cor.2005.05.034.

[4]

C. J. Liao, D. L. Shyur and C. H. Lin, Makespan minimization for two parallel machines with an availability constraint, European journal of operational Research, 160 (2005), 445-456. doi: 10.1016/j.ejor.2003.08.034.

[5]

C. J. Liao and W. J. Chen, Single-machine scheduling with periodic maintenance and nonresumable jobs, Computers & operations Research, 30 (2003), 1335-1347. doi: 10.1016/S0305-0548(02)00074-6.

[6]

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

[7]

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

[8]

G. Wang and T. C. E. Cheng, Heuristics for two-machine no-wait flowshop scheduling with an availability constraint, Information Processing Letters, 80 (2001), 305-309. doi: 10.1016/S0020-0190(01)00181-8.

[9]

D. H. Xu, Z. M. Cheng, Y. Q. Yin and H. X. Li, Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Computer & Operations Research, 36 (2009), 1809-1812. doi: 10.1016/j.cor.2008.05.001.

[10]

M. Y. Yue, A simple proof of the inequality $FFD(L)\leq \frac{11}{9}OPT(L)+1,\forall L$ for the FFD Bin-Packing algorithm, Acta Mathematics Application Sinica, 7 (1991), 321-331. doi: 10.1007/BF02009683.

show all references

References:
[1]

T. C. E. Cheng and G. Wang, An improved heuristic for two-machine flowshop scheduling with an availability constraint, Operation Research Letters, 26 (2000), 223-229. doi: 10.1016/S0167-6377(00)00033-X.

[2]

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

[3]

M. Ji, Y. He and T. C. E. Cheng, Single-machine scheduling with periodic maintenance to minimize makespan, Computer & Operations Research, 34 (2007), 1764-1770. doi: 10.1016/j.cor.2005.05.034.

[4]

C. J. Liao, D. L. Shyur and C. H. Lin, Makespan minimization for two parallel machines with an availability constraint, European journal of operational Research, 160 (2005), 445-456. doi: 10.1016/j.ejor.2003.08.034.

[5]

C. J. Liao and W. J. Chen, Single-machine scheduling with periodic maintenance and nonresumable jobs, Computers & operations Research, 30 (2003), 1335-1347. doi: 10.1016/S0305-0548(02)00074-6.

[6]

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

[7]

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

[8]

G. Wang and T. C. E. Cheng, Heuristics for two-machine no-wait flowshop scheduling with an availability constraint, Information Processing Letters, 80 (2001), 305-309. doi: 10.1016/S0020-0190(01)00181-8.

[9]

D. H. Xu, Z. M. Cheng, Y. Q. Yin and H. X. Li, Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Computer & Operations Research, 36 (2009), 1809-1812. doi: 10.1016/j.cor.2008.05.001.

[10]

M. Y. Yue, A simple proof of the inequality $FFD(L)\leq \frac{11}{9}OPT(L)+1,\forall L$ for the FFD Bin-Packing algorithm, Acta Mathematics Application Sinica, 7 (1991), 321-331. doi: 10.1007/BF02009683.

[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, 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

[3]

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

[4]

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

[5]

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

[6]

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

[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 and Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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 and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[16]

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 and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030

[17]

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 and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[18]

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

[19]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021144

[20]

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

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (125)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]