Algorithmic Approaches to Setup Minimization

descriptionPublicationkeyboard_double_arrow_right Article 01 Nov 1985 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 14, pages 954-965 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Ulrich Faigle; Gerhard Gierz; Rainer Schrader;

doi: 10.1137/0214068

Algorithmic Approaches to Setup Minimization

- Summary
- Subjects
- Metrics

Abstract

Constructions of classes of ordered sets are given for which the setup minimization problem can be solved by an efficient algorithm. Those constructions generalize series-parallel connections. Special classes of ordered sets are exhibited for which the greedy algorithm yields an optimal linear extension. In particular, it is shown that the class of N- free ordered sets is both defect optimal and strongly greedy.

Keywords

series-parallel connections, partially ordered sets, Analysis of algorithms and problem complexity, greedy algorithm, scheduling, N-free ordered sets, NP-complete problems, Performance evaluation, queueing, and scheduling in the context of computer systems

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	12
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%