Two-machine scheduling with periodic availability constraints to minimize makespan

Ganggang Li; Xiwen Lu

doi:10.3934/jimo.2015.11.685

Article Contents

2015, Volume 11, Issue 2: 685-700. Doi: 10.3934/jimo.2015.11.685

This issue Previous Article Scalarizations and Lagrange multipliers for approximate solutions in the vector optimization problems with set-valued maps Next Article

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

Received: October 31, 2013

Revised: April 30, 2014

Published: March 2015

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B35.

Citation:

Related Papers

Cited by

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.