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

Authors: Mohammad Rohaninejad; Rashed Sahraeian; Behdin Vahedi Nouri

Addresses: Department of Industrial Engineering, College of Engineering, Shahed University, Tehran, Iran ' Department of Industrial Engineering, College of Engineering, Shahed University, Tehran, Iran ' Department of Industrial Engineering, College of Engineering, Bu-Ali Sina University, Hamadan, Iran

Abstract: 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.

Keywords: capacitated job shop scheduling; genetic algorithm; firefly algorithm; shifting procedure; Taguchi method; industrial and systems engineering.

DOI: 10.1504/IJISE.2017.084421

International Journal of Industrial and Systems Engineering, 2017 Vol.26 No.3, pp.318 - 343

Received: 22 Oct 2014
Accepted: 06 Jun 2015
Published online: 07 Jun 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article