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

38 Citations (Scopus)


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
Issue number5
Early online date1 Oct 2012
Publication statusPublished - 1 May 2013
Externally publishedYes


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