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

Yige Sun, Sai-Ho Chung, Xin Wen and Hoi-Lam Ma

Transportation Research Part E: Logistics and Transportation Review, 2021, vol. 149, issue C

Abstract: 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.

Keywords: Robot-driven production lines; Job-shop scheduling; Deadlock; Machine blocking; Robot movement; Mixed integer linear programming (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554521000491
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:149:y:2021:i:c:s1366554521000491

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2021.102273

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().