Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6892950 | Computers & Operations Research | 2014 | 13 Pages |
Abstract
This paper addresses a robotic cell rescheduling problem and focuses on trade-off between the total completion time of all jobs and the disturbance of a reschedule. We first define and measure the disturbance of a reschedule as the deviation of completion time of the jobs already scheduled between the reschedule and the initial schedule. To guarantee the steady performance of the system, we consider a special case that the processing sequence of the jobs already scheduled cannot be changed. The addressed rescheduling problem is transformed into a series of deterministic local scheduling problems with the objective of minimizing the total completion time of all jobs provided that the disturbance is within a given limit. A two-phase branch and bound algorithm is developed to efficiently solve the local scheduling problems. To improve the efficiency of the search procedure, a dynamic enumeration mechanism is applied to eliminate redundant constraints. Furthermore, two search strategies are proposed to direct the search procedure toward finding an optimal solution and a near-optimal solution. Finally, computational results demonstrate the efficiency of our algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Pengyu Yan, Ada Che, Xiaoqiang Cai, Xiaowo Tang,