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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Set OpenAlex properties.
 
(5 intermediate revisions by 4 users not shown)
Property / reviewed by
 
Property / reviewed by: Milan Vlach / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Milan Vlach / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of Task Sequencing with Deadlines, Set-Up Times and Changeover Costs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Complexity of Scheduling with Batch Setup Times / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sequencing with Series-Parallel Precedence Constraints / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0377-2217(91)90250-y / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1975973671 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 11:07, 30 July 2024

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

    Identifiers