Volume 53, Number 1, January-March 2019
|Page(s)||111 - 128|
|Published online||31 January 2019|
The cycle shop scheduling: mathematical model, properties and solution algorithms
Department of Industrial Engineering, Faculty of Engineering, Kharazmi University,
2 Department of Mechanical, Automotive, and Materials, Faculty of Engineering, University of Windsor, Windsor, ON, Canada.
3 Department of Systems Science and Industrial Engineering, State University of New York at Binghamton, New York, USA.
* Corresponding author: firstname.lastname@example.org
Accepted: 3 November 2017
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.
Mathematics Subject Classification: 90C11 / 90C59
Key words: Scheduling / cycle shop / mixed integer linear programming model / metaheuristic algorithm / constructive heuristics
© EDP Sciences, ROADEF, SMAI 2019
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.