Abstract

The flexible job shop scheduling problem is NP-hard problem. There is no efficient technique to check the optimality of the solution of the flexible job shop scheduling problem. So, in this paper, theorems and lemmas for defining some optimality conditions for the solution of the flexible job shop scheduling problem are introduced. In addition, a mathematical model of the primal problem of the flexible job shop scheduling problem is introduced where the objective is to minimize the makespan. The dual problem of the primal problem is defined which is called Abdou’s problem. The relation between the optimal value of the primal problem and the optimal value of Abdou’s problem is proofed. The difference between the optimal solution of Abdou’s problem and any solution of the primal problem could be used as a quality measurement.

Key words: Scheduling, flexible job shop, mathematical model, optimality conditions.