Sharif University of Technology Scientia Iranica 1026-3098 27 2 2020 04 01 The stage shop scheduling problem: lower bound and metaheuristic 862 879 21119 10.24200/sci.2018.5199.1146 EN M.M. Nasiri School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran M. Hamid School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran Journal Article 2017 10 02 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. https://scientiairanica.sharif.edu/article_21119_50205ecc975ce43db0505ca7e11c83e1.pdf