Esswein, Carl, Billaut, Jean-Charles and Strusevich, Vitaly A. (2005) Two-machine shop scheduling: Compromise between flexibility and makespan value. European Journal of Operational Research, 167 (3). pp. 796-809. ISSN 0377-2217 (Print), 0377-2217 (Online) (doi:10.1016/j.ejor.2004.01.029)

Full text not available from this repository.

Abstract

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

Item Type:	Article
Uncontrolled Keywords:	scheduling, flexibility, robustness, flow shop, job shop, open shop
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/867

Actions (login required)

View Item