On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements
From MaRDI portal
Publication:2149603
DOI10.1007/S10898-021-01097-WzbMATH Open1495.90075arXiv2106.14692OpenAlexW3205093017MaRDI QIDQ2149603FDOQ2149603
Authors: Alexander Kononov, Julia Memar, Yakov Zinder 
Publication date: 29 June 2022
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: The paper is concerned with the two-machine flow shop, where each job requires an additional resource (referred to as storage space) from the start of its first operation till the end of its second operation. The storage requirement of a job is determined by the processing time of its first operation. At any point in time, the total consumption of this additional resource cannot exceed a given limit (referred to as the storage capacity). The goal is to minimise the makespan, i.e. to minimise the time needed for the completion of all jobs. This problem is NP-hard in the strong sense. The paper analyses how the parameter - a lower bound on the storage capacity specified in terms of the processing times, affects the computational complexity.
Full work available at URL: https://arxiv.org/abs/2106.14692
Recommendations
- A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
- Flow shop with job-dependent buffer requirements -- a polynomial-time algorithm and efficient heuristics
- A flowshop scheduling problem with two operations per job
- Minimizing Makespan In Flowshops With Pallet Requirements: Computational Complexity
Cites Work
- Optimal two- and three-stage production schedules with set-up time included
- The variable neighborhood search for the two machine flow shop problem with a passive prefetch
- Scheduling subject to resource constraints: Classification and complexity
- Scheduling for data gathering networks with data compression
- Flow-shop problems with intermediate buffers
- Flowshop scheduling with limited temporary storage
- Simple heuristics for scheduling with limited intermediate storage
- Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications
- A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations
- Scheduling. Theory, algorithms, and systems
- Permutation schedules for a two-machine flow shop with storage
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
- Flow shop with job-dependent buffer requirements -- a polynomial-time algorithm and efficient heuristics
- A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
- Flexible flow shop with dedicated buffers
- Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements
Cited In (4)
- A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
- Algorithms for flow shop with job-dependent buffer requirements
- Special issue: 18th international conference on mathematical optimization theory and operations research (MOTOR 2019)
- An exact borderline between the NP-hard and polynomial-time solvable cases of flow shop scheduling with job-dependent storage requirements
This page was built for publication: On a borderline between the NP-hard and polynomial-time solvable cases of the flow shop with job-dependent storage requirements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149603)
