Approximation results for the two-machine job shop under limited machine availability

被引：2

作者：

Hadda H. ^{[1
]}

机构：

[1] Unité de recherche OASIS, Ecole Nationale d’Ingénieurs de Tunis, Université de Tunis El Manar, BP 37, Le belvédère, Tunis

来源：

OPSEARCH | 2017年 / 54卷 / 3期

关键词：

Approximation schemes; Availability constraint; Flow shop; Job shop; Scheduling;

D O I：

10.1007/s12597-017-0298-5

中图分类号：

学科分类号：

摘要：

This paper tackles the two-machine job shop scheduling problem with limited machine availability under the resumable scenario. We provide a number of characterizations for the optimal solution. We also develop polynomial-time approximation schemes for two particular configurations and identify a polynomially solvable case. © 2017, Operational Research Society of India.

引用

页码：651 / 662

页数：11

共 24 条

[1]

Breit J., An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint, Inf. Process. Lett., 90, pp. 273-278, (2004)

[2]

Cheng T.C.E., Wang G., Two-machine flowshop scheduling with consecutive availability constraints, Inf. Process. Lett., 71, pp. 49-54, (1999)

[3]

Cheng T.C.E., Wang G., An improved heuristic for two-machine flowshop scheduling with an availability constraint, Oper. Res. Lett., 26, pp. 223-229, (2000)

[4]

Garey M.R., Johnson D.S., Computers and Intractability, Freeman, San Francisco, 8, pp. 87-99, (1979)

[5]

Golmakani H.R., Namazi A., An artificial immune algorithm for multiple-route job shop scheduling problem with preventive maintenance constraints, Int. J. Oper. Res., 19, pp. 457-478, (2014)

[6]

Gonzalez T., Sahni S., Flowshop and jobshop schedules: complexity and approximation, Oper. Res., 26, pp. 36-52, (1978)

[7]

Hadda H., A (43)-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints, Optim. Lett., 3, pp. 583-592, (2009)

[8]

Hadda H., An improved algorithm for the two machine flow shop problem with several availability constraints. 4OR-Q, J Oper. Res., 8, pp. 271-280, (2010)

[9]

Hadda H., A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints, Optim. Lett., 6, pp. 559-569, (2012)

[10]

Hadda H., A PTAS for a particular case of the two-machine flow shop with limited machine availability, J. Math. Model. Algorithm Oper. Res., 13, pp. 511-522, (2014)

← 1 2 3 →