Minimising the total cost of tardiness and overtime in a resumable capacitated job shop scheduling problem by using an efficient hybrid algorithm

This paper investigates a resumable capacitated job shop scheduling problem (CJSSP) that can have considerable applications in heavy industries where the job processing times are prolonged. Hence, this type of scheduling is somewhat classified as medium and long-term scheduling problem, in which the limited capacity of machineries cannot be overlooked. In order to formulate the problem a new mixed-integer linear programming (MILP) model with the objective of minimising the total cost of tardiness and overtime is presented. Since the problem is a Non-deterministic Polynomial-time hard (NP-Hard) problem, an effective hybrid meta-heuristic based on the genetic and firefly algorithms are developed to tackle its complexity in a reasonable time. In addition, two heuristic algorithms rooted in the shifting and Lagrangean procedures are proposed to guide the search process toward the feasible points of a given problem. For the sake of obtaining better and more robust solutions, the Taguchi method is also used to calibrate the parameters of the algorithm. Furthermore, numerical experiments are provided for evaluating the performance and effectiveness of the solution method. Regarding to the computational result, the efficiency of the proposed hybrid metaheuristic is evident, especially on solving medium and large-sized problems.