HEURISTIC ALGORITHMS FOR SCHEDULING IN A MULTIPROCESSOR TWO-STAGE FLOWSHOP WITH 0-1 RESOURCE REQUIREMENTS

Ewa Figielska

2007

Abstract

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0-1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which, while solving to optimality the resource constrained scheduling problem at the first stage of the flowshop, select for simultaneous processing jobs according to rules promising a good (short) schedule in the flowshop. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing their solutions with the lower bound on the optimal makespan. The results of computational experiments show that these heuristics are able to produce near-optimal solutions in short computation time.

Paper Citation

in Harvard Style

Figielska E. (2007). HEURISTIC ALGORITHMS FOR SCHEDULING IN A MULTIPROCESSOR TWO-STAGE FLOWSHOP WITH 0-1 RESOURCE REQUIREMENTS . In Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 978-972-8865-82-5, pages 452-455. DOI: 10.5220/0001643404520455

in Bibtex Style

@conference{icinco07,
author={Ewa Figielska},
title={HEURISTIC ALGORITHMS FOR SCHEDULING IN A MULTIPROCESSOR TWO-STAGE FLOWSHOP WITH 0-1 RESOURCE REQUIREMENTS},
booktitle={Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2007},
pages={452-455},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001643404520455},
isbn={978-972-8865-82-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - HEURISTIC ALGORITHMS FOR SCHEDULING IN A MULTIPROCESSOR TWO-STAGE FLOWSHOP WITH 0-1 RESOURCE REQUIREMENTS
SN - 978-972-8865-82-5
AU - Figielska E.
PY - 2007
SP - 452
EP - 455
DO - 10.5220/0001643404520455