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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1002/net.20452 | Networks |
Keywords | Field | DocType |
convex hull,job set,following scheduling problem,total revenue,wiley periodicals,polyhedral study,one-machine schedule,jobs completion time,indivisible job,inc. networks,unit job,revenue function | Revenue,Mathematical optimization,Job shop scheduling,Scheduling (computing),Convex hull,Inequality,Total revenue,Mathematics | Journal |
Volume | Issue | ISSN |
58 | 2 | 0028-3045 |
Citations | PageRank | References |
1 | 0.37 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Claudio Arbib | 1 | 119 | 22.41 |
martine labbe | 2 | 1238 | 108.61 |
Mara Servilio | 3 | 18 | 4.68 |