Flow Shop Scheduling with Inter-Stage Flexibility and Blocking Constraints
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908539046330368 |
|---|---|
| author | Nicosia, Gaia Pacifici, Andrea Pferschy, Ulrich Russo, Anna Russo Salvatore, Cecilia |
| author_facet | Nicosia, Gaia Pacifici, Andrea Pferschy, Ulrich Russo, Anna Russo Salvatore, Cecilia |
| contents | We investigate a scheduling problem arising from a material handling and processing problem in a production line of an Austrian company building prefabricated house walls. The addressed problem is a permutation flow shop with blocking constraints in which the machine of at least one stage can process a number operations of two other stages in the system. This situation is usually referred to as multi-task or inter-stage flexibility. The problem is in general NP-hard, but we derive a number of special cases that can be solved in polynomial time. For the general case, we present a variety of heuristic algorithms, with a focus on matheuristics that are grounded in two different mixed-integer linear programming (MIP) formulations of the problem. These matheuristics leverage the strengths of exact optimization techniques while introducing flexibility to address limits on computation time. To assess the performance of the proposed approaches, we conduct an extensive computational study on randomly generated test cases based on real-world instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18381 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Flow Shop Scheduling with Inter-Stage Flexibility and Blocking Constraints Nicosia, Gaia Pacifici, Andrea Pferschy, Ulrich Russo, Anna Russo Salvatore, Cecilia Optimization and Control Discrete Mathematics 90B35 (Primary) 90C59, 65Y20 (Secondary) G.2.3; F.2.2 We investigate a scheduling problem arising from a material handling and processing problem in a production line of an Austrian company building prefabricated house walls. The addressed problem is a permutation flow shop with blocking constraints in which the machine of at least one stage can process a number operations of two other stages in the system. This situation is usually referred to as multi-task or inter-stage flexibility. The problem is in general NP-hard, but we derive a number of special cases that can be solved in polynomial time. For the general case, we present a variety of heuristic algorithms, with a focus on matheuristics that are grounded in two different mixed-integer linear programming (MIP) formulations of the problem. These matheuristics leverage the strengths of exact optimization techniques while introducing flexibility to address limits on computation time. To assess the performance of the proposed approaches, we conduct an extensive computational study on randomly generated test cases based on real-world instances. |
| title | Flow Shop Scheduling with Inter-Stage Flexibility and Blocking Constraints |
| topic | Optimization and Control Discrete Mathematics 90B35 (Primary) 90C59, 65Y20 (Secondary) G.2.3; F.2.2 |
| url | https://arxiv.org/abs/2411.18381 |