Solution Representation in Proportionate Multiprocessor Open Shop

Abstract

Proportionate multiprocessor open shop is considered in this study. It is a shop model where a set of jobs follow no predefined route to visit several stages with at least one having two or more parallel machines to carry out the same task. Proportionality means that processing times depend only on stages and are independent of jobs, hence is defined as stage-wise. The shop model has various application areas in industry but the literature on the field is still limited. In this study, a novel solution representation scheme is proposed for the proportionate multiprocessor open shop. The scheme is based on permutation of stages and encodes the cumulative number of job assignments to a stage. The proposed scheme is shown to generate higher quality random solutions compared to the common operation permutation representation for the shop model. The approach proposed in this study to design a solution representation for a scheduling problem is a new and favorable approach that takes into account the specific machine environment, job characteristics and objective function of the problem under consideration. This way of designing solution representation schemes would increase the solution quality or decrease the computational time required in solution algorithms for scheduling problems.