Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches

Soroush Fatemi-Anaraki, Reza Tavakkoli-Moghaddam, Mehdi Foumani*, Behdin Vahedi-Nouri

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)

Abstract

This paper investigates a dynamic scheduling problem within a job shop robotic cell, wherein multiple robotic arms are responsible for material handling in a U-shaped arrangement. Each robotic arm has access to specific workstations based on their distance in the cell layout. Therefore, a part may need to be exchanged between several robots according to its process plan. For this purpose, intermediate buffers are positioned between each pair of consecutive robots. Due to the dynamic nature of the problem, new jobs arrive at unpredictable times, which in turn necessitates rescheduling taking the system's current state into account. To tackle this problem, firstly, a Mixed-Integer Linear Programming (MILP) model is devised. Secondly, three distinct Speed-up Constraints (SCs) derived from the problem's inherent characteristics are designed and implemented to accelerate the MILP model's solving procedure. Afterward, the problem is formulated using Constraint Programming (CP) approach. The performance of the CP model and the MILP model in presence of all possible combinations of the SCs are evaluated and compared through solving various random instances. Next, an analysis is performed on the buffers’ pick-up criterion and how it is affected by the problem's size. Besides, the impact of changes in the robots’ speed on the productivity of the cell is assessed. Finally, the extent to which the rescheduling priority affects the output of the model is studied.

Original languageEnglish
Article number102770
JournalOmega (United Kingdom)
Volume115
DOIs
Publication statusPublished - Feb 2023
Externally publishedYes

Keywords

  • Constraint programming
  • Dynamic scheduling
  • Job shop robotic cell
  • Material handling
  • Mixed-integer linear programming

Fingerprint

Dive into the research topics of 'Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches'. Together they form a unique fingerprint.

Cite this