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

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences