On the Status of Irreducibility Problems of Open Shop Sequencing Problems

Abstract

In an open shop scheduling problem (OSSP) one of the major tasks is to minimize the makespan over the sequences. It has practical values, for instance, in manufacturing, service industries, communication, and facility assignments. The concept of irreducibility has proven one of the most important and fertile research topics as the set of all irreducible sequences attains optimality independent of processing times. This work presents the recent complexity status of irreducibility of OS sequences. The recent works give encouraging results. The results obtained in past several years are viewed with useful hints for the developments of exact or heuristic algorithms and generalize the idea to general regular objectives.

Key words: scheduling/sequencing theory; open shop; reducibility; potential optimality; complexity

DOI: 10.3126/njst.v11i0.4147

Nepal Journal of Science and Technology 11 (2010) 205-214