A genetic algorithm for the proportionate multiprocessor open shop

The multiprocessor open shop (MPOS) scheduling problem is NP-complete, a category of hard combinatorial optimization problems that have not received much attention in the literature. In this work, a special MPOS—a proportionate one—is introduced for the first time. Two original mixed integer programming formulations for the proportionate MPOS are developed and their complexity is discussed. Due to the complexity of the MPOS, this paper develops a compu-search methodology (a genetic algorithm (GA)) to schedule the shop with the objective of minimizing the makespan. In this novel GA, a clever chromosome representation of a schedule is developed that succinctly encodes a schedule of jobs across multiple stages. The innovative design of this chromosome enables any permutation of its genes to yield a feasible solution. This simple representation of an otherwise very complex schedule enables the genetic operators of crossover and mutation to easily manipulate a schedule as the algorithm iteratively searches for better schedules. A testbed of difficult instances of the problem are created to evaluate the performance of the GA. The solution for each instance is compared with a derived lower bound. Computational results reveal that the algorithm performs extremely well, demonstrating its potential to efficiently schedule MPOS problems. More importantly, successful experiments on large-scale problem instances suggest the readiness of the GA for industrial use.