MINIMIZING THE MAKESPAN IN TWO-MACHINE JOB SHOP SCHEDULING PROBLEMS WITH NO MACHINE IDLE-TIME

Fatma Hermès, Jacques Carlier, Aziz Moukrim, Khaled Ghédira

2009

Abstract

This paper deals with two-machine job shop scheduling problems working under the no-idle constraint, that is, machines must work continuously without idle intervals. The makespan (Cmax) has to be minimized. First, we study the problem where each job consists of at most two operations and we show that it can be solved polynomially using Jackson’s rule (Jackson, 1956). Second, we study the problem where the number of operations per job can be greater than two and all operations are of unit time and we extend the results of (Hefetz and Adiri, 1982). Finally, we discuss the possibility of getting feasible solutions and then optimal solutions in the general case where the number of operations per job can be greater than two and all operations do not have the same processing time.

Paper Citation

in Harvard Style

Hermès F., Carlier J., Moukrim A. and Ghédira K. (2009). MINIMIZING THE MAKESPAN IN TWO-MACHINE JOB SHOP SCHEDULING PROBLEMS WITH NO MACHINE IDLE-TIME . In Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO, ISBN 978-989-8111-99-9, pages 89-96. DOI: 10.5220/0002213500890096

in Bibtex Style

@conference{icinco09,
author={Fatma Hermès and Jacques Carlier and Aziz Moukrim and Khaled Ghédira},
title={MINIMIZING THE MAKESPAN IN TWO-MACHINE JOB SHOP SCHEDULING PROBLEMS WITH NO MACHINE IDLE-TIME},
booktitle={Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,},
year={2009},
pages={89-96},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002213500890096},
isbn={978-989-8111-99-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Volume 3: ICINCO,
TI - MINIMIZING THE MAKESPAN IN TWO-MACHINE JOB SHOP SCHEDULING PROBLEMS WITH NO MACHINE IDLE-TIME
SN - 978-989-8111-99-9
AU - Hermès F.
AU - Carlier J.
AU - Moukrim A.
AU - Ghédira K.
PY - 2009
SP - 89
EP - 96
DO - 10.5220/0002213500890096