### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 335-357 |

Number of pages | 23 |

Journal | Journal of Scheduling |

Volume | 22 |

Issue number | 3 |

DOIs | |

Publication status | Published - 15 Jun 2019 |

### Fingerprint

### Keywords

- Complexity
- Machine scheduling
- Machine sequence
- Parallel batching machine

### Cite this

*Journal of Scheduling*,

*22*(3), 335-357. https://doi.org/10.1007/s10951-018-0560-6

}

*Journal of Scheduling*, vol. 22, no. 3, pp. 335-357. https://doi.org/10.1007/s10951-018-0560-6

**Scheduling parallel batching machines in a sequence.** / Passchyn, Ward (Corresponding author); Spieksma, Frits C.R.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Scheduling parallel batching machines in a sequence

AU - Passchyn, Ward

AU - Spieksma, Frits C.R.

PY - 2019/6/15

Y1 - 2019/6/15

N2 - 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.

AB - 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.

KW - Complexity

KW - Machine scheduling

KW - Machine sequence

KW - Parallel batching machine

UR - http://www.scopus.com/inward/record.url?scp=85044178120&partnerID=8YFLogxK

U2 - 10.1007/s10951-018-0560-6

DO - 10.1007/s10951-018-0560-6

M3 - Article

AN - SCOPUS:85044178120

VL - 22

SP - 335

EP - 357

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 3

ER -