A hybrid discrete differential evolution algorithm for dynamic scheduling in robotic cells

摘要

This paper addresses a dynamic scheduling problem in robotic cells, where a computer-controlled robot is responsible for handling materials between workstations. In such automated manufacturing systems, efficiently scheduling transportations of the material plays an important role in improving the throughput of the system. We consider an uncertain setting where more than one new jobs arrive at the system and need to be scheduled immediately. To reduce the disturbance occurred by frequently rescheduling or adjusting the existing schedule, we keep the existing schedule unchanged and insert the new jobs' processing operations and transportations into the available(idle) time intervals of the workstations and the robot, respectively. To get an optimal new schedule, the problem is formulated as a mixed integer programming model with the objective that minimizes the total completion time of the new jobs. As the NP-hard nature of the problem, a hybrid discrete differential evolution (DDE) algorithm is proposed to search for a near-optimal solution within a reasonable computational time. In the hybrid DDE, a extension heuristic method is developed to generate a local optimal solution provided that a new jobs inserting sequence is given, and the DDE is applied to search for an optimal or near-optimal new jobs inserting sequence. The computational results indicate that the hybrid DDE runs effectively to search for the optimal or near-optimal new schedules.