Scheduling parallel batching machines in a sequence

Ward Passchyn (Corresponding author), Frits C.R. Spieksma

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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.

TaalEngels
Pagina's335-357
Aantal pagina's23
TijdschriftJournal of Scheduling
Volume22
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 1 jun 2019

Vingerafdruk

Computational complexity
Scheduling
Hardness
Polynomials
Batching

Trefwoorden

    Citeer dit

    @article{367e5f1b20d84220a98c795a23338d23,
    title = "Scheduling parallel batching machines in a sequence",
    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.",
    keywords = "Complexity, Machine scheduling, Machine sequence, Parallel batching machine",
    author = "Ward Passchyn and Spieksma, {Frits C.R.}",
    year = "2019",
    month = "6",
    day = "1",
    doi = "10.1007/s10951-018-0560-6",
    language = "English",
    volume = "22",
    pages = "335--357",
    journal = "Journal of Scheduling",
    issn = "1094-6136",
    publisher = "Springer",
    number = "3",

    }

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

    In: Journal of Scheduling, Vol. 22, Nr. 3, 01.06.2019, blz. 335-357.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - Scheduling parallel batching machines in a sequence

    AU - Passchyn,Ward

    AU - Spieksma,Frits C.R.

    PY - 2019/6/1

    Y1 - 2019/6/1

    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

    VL - 22

    SP - 335

    EP - 357

    JO - Journal of Scheduling

    T2 - Journal of Scheduling

    JF - Journal of Scheduling

    SN - 1094-6136

    IS - 3

    ER -