A Tabu search algorithm for the open shop scheduling problem with sequence dependent setup times

The impact of setup on manufacturing performance, and the scarce research on the scheduling of the open shop with sequence dependent setup times have motivated this research. The open shop consist of a set of n jobs each one requiring m operations to be processed on a set of m machines, one operation per machine. Each operation has a fixed duration time. To process a job on a machine a setup is required whose duration depends on both the job just processed and the job to be processed. The problem consist on fording an order of processing operations of jobs on the machines with the objective to minimize the longest time to finish the schedule or the makespan. The problem is modeled by a disjunctive graph. To find the best solution for this problem an algorithm combining Tabu search and a longest path algorithm is proposed.; The initial solution is generated by a proposed dispatching rule and by random. On every iteration a critical path is computed. The algorithm is based on the selection of moves from blocks of operations along this critical path. The neighborhood is generated by moves whose operations are processed by the same machine and by moves whose operations belong to the same job. A procedure to reduce the amount of computations resulting in the evaluation of each move is implemented. For this end we have developed a procedure based on the inverse topological order of operations in a graph. At the end of every iteration the best move is selected.; To further improve the search an intensification strategy is implemented by restarting the search from previous best solutions. The algorithm detect potential cycles in the solution, stopping the search once a probable cycle is detected, and transferring the search to the intensification strategy.; The algorithm has been tested with a set of random generated problems and two benchmark problems from literature.