Modeling and scheduling no-wait open shop problems

This paper studies the problem of scheduling open shops with no intermediate buffer, called no-wait open shops under makespan minimization. No-wait scheduling problems arise in many realistic production environments such as hot metal rolling, the plastic molding, chemical and pharmaceutical, food processing and several other industries. To tackle such problems, we first develop three different mathematical models, mixed integer linear programs, by which we can solve the problem to optimality. Besides the models, we propose novel metaheuristics based on genetic and variable neighborhood search algorithms to solve the large-sized problems in an acceptable computational time. The key point in any scheduling solver is the procedure of encoding and decoding schemes. In this paper, we propose a simple yet effective tailor-made procedure of encoding and decoding schemes for no-wait open shop problems. The operators of the proposed metaheuristics are designed so as to consider the specific encoding scheme of the problem. To evaluate the performance of models and metaheuristics, we conduct two computational experiments. The first includes small-sized instances by which we compare the mathematical models and assess general performance of the proposed metaheuristics. In the second experiment, we further evaluate the potential of metaheuristics on solving some benchmarks in the literature of pure open shops. The results show that the models and metaheuristics are effective to deal with the no-wait open shop problems.