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
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.
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
- A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
- A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations
- Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements
- Flexible flow shop with dedicated buffers
- Flow shop with job-dependent buffer requirements -- a polynomial-time algorithm and efficient heuristics
- Flow-shop problems with intermediate buffers
- Flowshop scheduling with limited temporary storage
- Optimal two- and three-stage production schedules with set-up time included
- Permutation schedules for a two-machine flow shop with storage
- Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications
- Scheduling for data gathering networks with data compression
- Scheduling subject to resource constraints: Classification and complexity
- Scheduling. Theory, algorithms, and systems
- Simple heuristics for scheduling with limited intermediate storage
- The variable neighborhood search for the two machine flow shop problem with a passive prefetch
- Two-machine flow shops with an optimal permutation schedule under a storage constraint
Cited in
(4)- A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements
- Special issue: 18th international conference on mathematical optimization theory and operations research (MOTOR 2019)
- Algorithms for flow shop with job-dependent buffer requirements
- 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)
