.png){kind=icon}
.png){kind=icon}
Return
Two-machine robotic cell scheduling problem with sequence-dependent setup times
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2012.09.006.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2012 Elsevier Ltd. All rights reserved.
Keywords:
Robotic cell scheduling
Sequence-dependent setup times
Mixed-integer linear programming
Simulated annealing
Branch and bound
Taguchi
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W