Novel robotic job-shop scheduling models with deadlock and robot movement considerations

The robotic job-shop scheduling problem (RJSP) has become increasingly important due to the wide application of robots for material delivery in modern logistics and supply chain systems. With the common assumptions of negligible material transportation procedures and infinite machine buffers, the traditional job-shop scheduling problem (JSP) models can lead to system failures due to the potential deadlock for a robot-driven production line. In this study, we propose two novel robotic job-shop scheduling models with deadlock and robot movement considerations (RJSPDT). The proposed novel models simultaneously consider the scheduling of job operations and the movement of the robot, with the objective of minimizing makespan. In order to avoid deadlock, the machine blocking strategy is applied and a set of tight deadlock-avoidance constraints is proposed. Two modelling approaches are applied: the traditional position-based approach and the novel network-based approach which is inspired by aviation scheduling studies. Through numerical examples, it is illustrated that our proposed models can completely avoid transportation conflicts by considering deadlock and robot movement. Besides, through computational experiments, the network-based RJSPDT shows higher solution efficiency owing to the smaller model size than the position-based RJSPDT (e.g., reducing the computational time by 96% for small-scale problems). Moreover, we explore the impacts of job settings (e.g., number of jobs, number of operations in a job) and job entrance strategies (i.e., fixed entrance and flexible entrance) on model performances. Results show that the number of jobs imposes greater impacts than the number of operations in a job, while the fixed entrance strategy can reduce the average computational time by 60% with little impact on the makespan.