Scheduling parallel batching machines in a sequence
| Autor: | Ward Passchyn, Frits C. R. Spieksma |
|---|---|
| Přispěvatelé: | Discrete Mathematics, Combinatorial Optimization 1 |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Machine scheduling 021103 operations research Supply chain management Computational complexity theory Job shop scheduling Computer science 0211 other engineering and technologies General Engineering 0102 computer and information sciences 02 engineering and technology Complexity Management Science and Operations Research 01 natural sciences Scheduling (computing) Machine sequence Parallel batching machine 010201 computation theory & mathematics Artificial Intelligence Operations management Special case Time complexity Software |
| Zdroj: | Journal of Scheduling, 22(3), 335-357. Springer |
| ISSN: | 1094-6136 |
| Popis: | Motivated by the application of scheduling a sequence of locks along a waterway, we consider a scheduling problem where multiple parallel batching machines are arranged in a sequence and process jobs that travel along this sequence. We investigate the computational complexity of this problem. More specifically, we show that minimizing the sum of completion times is strongly NP-hard, even for two identical machines and when all jobs travel in the same direction. A second NP-hardness result is obtained for a different special case where jobs all travel at an identical speed. Additionally, we introduce a class of so-called synchronized schedules and investigate special cases where the existence of an optimum solution which is synchronized can be guaranteed. Finally, we reinforce the claim that bidirectional travel contributes fundamentally to the computational complexity of this problem by describing a polynomial time procedure for a setting with identical machines and where all jobs travel in the same direction at equal speed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink