Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times (Q1179195)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times
scientific article

    Statements

    Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times (English)
    0 references
    26 June 1992
    0 references
    The author considers the problem of minimizing maximum delivery time on a single machine under the assumption that the set of \(n\) jobs is partitioned into batches and a unit set-up time is associated with every switching from a job in one batch to a job in another batch. The problem is known to be NP-hard [see \textit{J. Bruno} and \textit{P. Downey}, SIAM J. Computing 7, 393-403 (1978; Zbl 0386.68050)]. Here, three polynomial-time approximation algorithms are presented and their worst-case behavior is analyzed.
    0 references
    0 references
    maximum delivery time
    0 references
    single machine
    0 references
    unit set-up time
    0 references
    NP-hard
    0 references
    polynomial-time approximation algorithms
    0 references
    worst-case behavior
    0 references
    0 references
    0 references