# American Institute of Mathematical Sciences

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 & 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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1007/BF02009683.  Google Scholar
 [1] 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 [2] Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174 [3] Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001 [4] Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071 [5] Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391 [6] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [7] Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013 [8] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [9] Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 [10] Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060 [11] Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088 [12] Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 [13] Editorial Office. Retraction: Xiaohong Zhu, Lihe Zhou, Zili Yang and Joyati Debnath, A new text information extraction algorithm of video image under multimedia environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1265-1265. doi: 10.3934/dcdss.2019087 [14] Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

2019 Impact Factor: 1.366

## Metrics

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

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]