Two-machine robotic cell scheduling problem with sequence-dependent setup times

M.H. Fazel Zarandi*, H. Mosadegh, M. Fattahi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

37 Citations (Scopus)

Abstract

In this paper, we introduce a new and practical two-machine robotic cell scheduling problem with sequence-dependent setup times (2RCSDST) along with different loading/unloading times for each part. Our objective is to simultaneously determine the sequence of robot moves and the sequence of parts that minimize the total cycle time. The proposed problem is proven to be strongly NP-hard. Using the Gilmore and Gomory (GnG) algorithm, a polynomial-time computable lower bound is provided.

Based on the input parameters, a dominance condition is developed to determine the optimal sequence of robot moves for a given sequence of parts. A mixed-integer linear programming (MILP) model is provided and enhanced using a valid inequality based on the given dominance condition. In addition, a branch and bound (BnB) algorithm is exploited to solve the problem, and due to the NP-hardness, an improved simulated annealing (SA) algorithm is proposed to address large-sized test problems.

All the solution methods are evaluated using small-, medium- and large-sized test problems. The numerical results indicate that the optimal solution of the MILP model is attained for the medium- and some large-sized test problems, and the proposed SA, tuned using the Taguchi technique, provides an acceptable, near-optimal solution with markedly reduced CPU time. Moreover, the lower bound is observed to be significantly near the optimal solution. Thus, this lower bound is exploited to validate the results of the SA algorithm for large-sized test problems.
Original languageEnglish
Pages (from-to)1420-1434
Number of pages15
JournalComputers and Operations Research
Volume40
Issue number5
Early online date1 Oct 2012
DOIs
Publication statusPublished - 1 May 2013
Externally publishedYes

Fingerprint

Dive into the research topics of 'Two-machine robotic cell scheduling problem with sequence-dependent setup times'. Together they form a unique fingerprint.

Cite this