An effective hybrid simulated annealing and two mixed integer linear formulations for just-in-time open shop scheduling problem

This paper addresses open shop scheduling problem from the viewpoint of just-in-time management in which the objective function is to minimize the sum of weighted earliness/tardiness penalties. The problem is formulated as two different mixed integer linear programming models. To solve the problem, a novel hybrid two-phase algorithm is presented. In the first phase, a simulated annealing is applied to search the appropriate sequences of jobs on machines. Based on the job sequences obtained in the first phase, one of the proposed mathematical formulations can be reduced to a linear programming model and in the second phase by solving the linear programming model, the start time of jobs on machines can be determined. In order to evaluate the quality of solutions, a specific branching strategy is applied in solving the other mathematical model to obtain a lower bound. Computational results show that the algorithm obtains high-quality solutions in reasonable time.