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

Arbib Claudio | Zendy; Labbé Martine | Zendy; Servilio Mara | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

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

Author(s) -

Arbib Claudio,

Labbé Martine,

Servilio Mara

Publication year - 2011

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.20452

Subject(s) - scheduling (production processes) , computer science , mathematical optimization , schedule , convex hull , job shop scheduling , set (abstract data type) , regular polygon , operations research , mathematics , geometry , programming language , operating system

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research