Operations Research 2025
Abstract Submission

199. Two-machine open shop with limited storage space

Invited abstract in session FA-3: Algorithms and Applications, stream Project Management and Scheduling.

Friday, 8:45-10:15
Room: H5

Authors (first author is the speaker)

1. Mateusz Dokowicz
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań
2. Joanna Berlińska
Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Poznań

Abstract

We study makespan minimization in a two-machine open shop with limited storage space. In order to be processed, each job requires a given amount of storage capacity, which is allocated as soon as its first operation begins, and released only after the completion of its second operation. Thus, the storage space is used by the job not only during the execution of its operations, but also in the interval between completing the first and starting the second operation. This distinguishes our problem from open shop scheduling with resource constraints studied in the existing literature. The storage space available in the system is limited, which means that a job may start being processed only if sufficient capacity is available. The goal is to determine time intervals for executing all operations so as to minimize the maximum completion time. We show that the problem is strongly NP-hard and formulate it as an integer linear program. Heuristic algorithms are proposed and their performance is analyzed in a series of computational experiments.

Acknowledgement: The research of the first author was supported by Adam Mickiewicz University, Poznan, under the Excellence Initiative – Research University Study@research grant 161/34/UAM/0041.

Keywords

Status: accepted

Back to the list of papers