Separation Algorithms for Single-Machine Scheduling with Precedence Constraints

hal.structure.identifier
dc.contributor.author	Mahjoub, Ali Ridha	*
hal.structure.identifier
dc.contributor.author	McCormick, S. Thomas	*
dc.date.accessioned	2010-04-28T10:08:07Z
dc.date.available	2010-04-28T10:08:07Z
dc.date.issued	2010
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/4026
dc.language.iso	en	en
dc.subject	Constraints	en
dc.subject.ddc	003	en
dc.title	Separation Algorithms for Single-Machine Scheduling with Precedence Constraints	en
dc.type	Communication / Conférence
dc.description.abstracten	In a 1991 paper M. Queyranne and Y. Wang proposed three classes of valid inequalities for the classic problem of scheduling a single machine with precedence constraints. These constraints are called "parallel constraints", "series constraints", and "Z constraints". It has been understood for a long time how to separate parallel constraints using submodular function minimization, or even just min cut, but separating series constraints has remained open since that time. We give a fast, practical separation algorithm for series constraints. It is based on parametric min cut algorithms. We also investigate separation of "Z constraints."	en
dc.description.sponsorshipprivate	oui	en
dc.subject.ddclabel	Recherche opérationnelle	en
dc.relation.conftitle	ISCO International Symposium on Combinatorial Optimization	en
dc.relation.confdate	2010-03
dc.relation.confcity	Hammamet	en
dc.relation.confcountry	Tunisie	en
hal.author.function	aut
hal.author.function	aut

Files in this item

Files	Size	Format	View
There are no files associated with this item.