Back to Search Start Over

Scheduling two chains of unit jobs on one machine: A polyhedral study

Authors :
Mara Servilio
Martine Labbé
Claudio Arbib
Fortz, Bernard
Graphes et Optimisation Mathématique [Bruxelles] (GOM)
Université libre de Bruxelles (ULB)
Source :
Networks (N.Y.N.Y., Print) 58 (2011): 103–113., info:cnr-pdr/source/autori:Arbib, C.; Labbè, M.; Servilio, M./titolo:Scheduling Two Chains of Unit Jobs on One Machine: A Polyhedral Study/doi:/rivista:Networks (N.Y.N.Y., Print)/anno:2011/pagina_da:103/pagina_a:113/intervallo_pagine:103–113/volume:58, Networks, Networks, Wiley, 2011, 58 (2), pp.103-113, Networks (N.Y.N.Y., Print) (2010)., info:cnr-pdr/source/autori:Arbib, C.; Labbé, M.; Servilio, M./titolo:Scheduling Two Chains of Unit Jobs on One Machine: A Polyhedral Study/doi:/rivista:Networks (N.Y.N.Y., Print)/anno:2010/pagina_da:/pagina_a:/intervallo_pagine:/volume
Publication Year :
2011
Publisher :
HAL CCSD, 2011.

Abstract

We investigate polyhedral properties of the following scheduling problem: given two sets of unit, indivisible jobs and revenue functions of the jobs completion times, find a one-machine schedule maximizing the total revenue under the constraint that the schedule of each job set respects a prescribed chain-like precedence relation. A solution to this problem is an order preserving assignment of the jobs to a set of time-slots. We study the convex hull of the feasible assignments and provide families of facet-defining inequalities in two cases: (i) each job must be assigned to a time-slot and (ii) a job does not need to be assigned to any time-slot. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011 © 2011 Wiley Periodicals, Inc.

Subjects

Subjects :
Convex hull
Mathematical optimization
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]
Computer Networks and Communications
one-machine scheduling
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
scheduling, polyhedral study
01 natural sciences
Scheduling (computing)
Revenue
Mathematics
021103 operations research
Job shop scheduling
convex hull
facet-defining inequalities
Total revenue
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Mathématiques
010201 computation theory & mathematics
Hardware and Architecture
Recherche opérationnelle
Software
Information Systems

Details

Language :
English
ISSN :
00283045 and 10970037
Database :
OpenAIRE
Journal :
Networks (N.Y.N.Y., Print) 58 (2011): 103–113., info:cnr-pdr/source/autori:Arbib, C.; Labbè, M.; Servilio, M./titolo:Scheduling Two Chains of Unit Jobs on One Machine: A Polyhedral Study/doi:/rivista:Networks (N.Y.N.Y., Print)/anno:2011/pagina_da:103/pagina_a:113/intervallo_pagine:103–113/volume:58, Networks, Networks, Wiley, 2011, 58 (2), pp.103-113, Networks (N.Y.N.Y., Print) (2010)., info:cnr-pdr/source/autori:Arbib, C.; Labbé, M.; Servilio, M./titolo:Scheduling Two Chains of Unit Jobs on One Machine: A Polyhedral Study/doi:/rivista:Networks (N.Y.N.Y., Print)/anno:2010/pagina_da:/pagina_a:/intervallo_pagine:/volume
Accession number :
edsair.doi.dedup.....f6e0a96e0c5fa8da158c62809d49dc53

Tools

Authors Abstract Subjects Details