Alternate Formulations of the Reducibility Problem of Open Shop Sequences Minimizing the Makespan

Abstract

The decision problem whether a given open shop sequence, minimizing the maximum completion time, is irreducible has been considered in the last 20 years. The problem has diversified applications in industries and communications. By now, a number of algorithms based on the specific properties of the corresponding sequence graph are proposed. Thus the problem is solved only partially and only in some special cases, but not in general yet. A number of open problems and conjectures carried out in this research have been posed, so far. In this paper, we present a brief sketch of these ideas with different formulations of the reducibility of open shop sequences and expose how important are the roles of conflict resolution reaching a conclusion to its end. Paths on the so-called H-comparability graphs with respect to the implication classes play vital roles in it.

Key words: Scheduling; Sequencing; Open shop; Comparability graph; reducibility; Complexity

DOI: http://dx.doi.org/10.3126/jie.v8i1-2.5117

Journal of the Institute of Engineering

Vol. 8, No. 1&2, 2010/2011

Page: 243-254

Uploaded Date: 20 July, 2011