The cycle shop scheduling: mathematical model, properties and solution algorithms

¹ Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran.
² Department of Mechanical, Automotive, and Materials, Faculty of Engineering, University of Windsor, Windsor, ON, Canada.
³ Department of Systems Science and Industrial Engineering, State University of New York at Binghamton, New York, USA.

^* Corresponding author: bahman.naderi@khu.ac.ir

Received: 4 February 2017
Accepted: 3 November 2017

Abstract

Conventionally, in scheduling problems it is assumed that each job visits each machine once. This paper studies a novel shop scheduling called cycle shop problems where jobs might return to each machine more than once. The problem is first formulated by two mixed integer linear programming models. The characteristics of the problem are analyzed, and it is realized that the problem suffers from a shortcoming called redundancy, i.e., several sequences represents the same schedule. In this regard, some properties are introduced by which the redundant sequences can be recognized before scheduling. Three constructive heuristics are developed. They are based on the shortest processing time first, insertion neighborhood search and non-delay schedules. Then, a metaheuristic based on scatter search is proposed. The algorithms are equipped with the redundancy prevention properties that greatly reduce the computational time of the algorithms. Two sets of experiments are conducted. The proposed model and algorithms are evaluated. The results show the high performance of model and algorithms.