Modeling and scheduling open shops with sequence-dependent setup times to minimize total completion time

It is known that in many real industrial settings, some setup is carried out before the process of a job. Usually, the magnitude of this setup depends on the order of two consecutive jobs. In this case, the setup is called sequence-dependent. This paper deals with open shop scheduling with sequence-dependent setup times to minimize the total completion time. The problem is formulated as an effective mixed integer linear programming model that best characterizes and solves to optimality small-sized instances of the problem under consideration. Since the electromagnetism-like metaheuristic (EM) is successfully applied to some NP-hard problems, we have been motivated to employ and assess the effectiveness of EM to solve the open shop with setup times. To further enhance EM, a local search engine in form of a fast and simple simulated annealing is incorporated. In order to evaluate the performance of the proposed algorithms, an experiment is designed where the proposed methods are compared against some algorithms in the literature. The related results are analyzed by statistical tools. The experimental results and statistical analyses demonstrate that the proposed model and EM are effective for the problem.