Solving a Multi-Resource Partial-Ordering Flexible Variant of the Job-Shop Scheduling Problem with Hybrid ASP

EasyChair Preprint 8641

Abstract

In many industries, scheduling is a key component to efficient management of resources and, thus, ensuring competitiveness and success of companies by minimizing the waste of time and money. In this work, we propose a Multi-resource Partial-ordering Flexible Job-shop Scheduling (MPFJSS) formulation to capture scheduling scenarios where partially-ordered sequences of operations must be scheduled on multiple required resources, such as tools and specialists. The resources are flexible and can process one or more operations based on their characteristics. We have built a model using Answer Set Programming (ASP) in which the execution time of operations is determined using Difference Logic. Furthermore, we introduced two multi-shot strategies that identify the time bounds and find a schedule while minimizing the total tardiness. We conducted experiments on a set of instances provided by a semiconductor manufacturer, and the results showed that the proposed model could find schedules for 87 out of 91 real-world instances.

Keyphrases: ASP, Multi-shot solving, Scheduling, difference logic

@booklet{EasyChair:8641,
  author    = {Giulia Francescutto and Konstantin Schekotihin and Mohammed M. S. El-Kholany},
  title     = {Solving a Multi-Resource Partial-Ordering Flexible Variant of the Job-Shop Scheduling Problem with Hybrid ASP},
  howpublished = {EasyChair Preprint 8641},
  year      = {EasyChair, 2022}}