The stage shop scheduling problem: lower bound and metaheuristic

Remarkable efforts are made to develop the job shop scheduling problem up to now. As a novel generalization, the stage shop can be defined as an environment, in which each job is composed of some stages and each stage may include one operation or more. A stage can be defined a subset of operations of a job, such that these operations can be done in any arbitrary relative order while the stages should be processed in a predetermined order. In other words, the operations of a stage cannot be initiated until all operations of the prior stage are completed. In this paper, an innovative lower bound based on solving the preemptive open shop (using a linear programming model in polynomial time) is devised for the makespan in a stage shop problem. In addition, three metaheuristics, including firefly, harmony search and water wave optimization algorithms are applied to the problem. The results of the algorithms are compared with each other, the proposed lower bound, and a commercial solver.