American Institute of Mathematical Sciences

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

Two-machine scheduling with periodic availability constraints to minimize makespan

Ganggang Li 1, and  Xiwen Lu 1,

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.
Keywords: availability constraint, nonresumable, Scheduling, resumable, algorithm..
Mathematics Subject Classification: Primary: 90B3.
Citation: 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
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.  Google Scholar

[2]

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

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

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

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

[6]

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

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

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

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

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

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

[2]

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

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

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

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

[6]

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

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

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

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

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

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

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

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

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

Jingwen Zhang, Wanjun Liu, Wanlin Liu. An efficient genetic algorithm for decentralized multi-project scheduling with resource transfers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020140
[8]

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

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

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

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

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

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

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

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

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

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

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

Michel Lavrauw, Geertrui Van de Voorde. Locally repairable codes with high availability based on generalised quadrangles. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020099
[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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences