New algorithm of scheduling based on prioriry rules on machines to solve bi-criteria blocking job shop scheduling problem

摘要

In this paper we study the bi-criteria blocking job shop scheduling problem. The objective is to simultaneously minimize two criteria: the Makespan and the maximum lateness. The blocking occurs when the intermediate buffer for storing completed operations between machines does not exist. We have proposed two Metaheuristics so as to find a set of non-dominated solutions. The first one is the tabu search which consists in the minimization of one criterion while the second criterion is bounded, and the second one is the tabu search based on the minimization of a linear combination of criteria. To assure the assignment of operations to their machines, we propose a new method which is based on application of priority rules on machines. This work is tested on benchmark instances from job shop literature and the results are presented and discussed.