Loading...
Please wait, while we are loading the content...
Similar Documents
Tepper School of Business 1984 On the facial structure of scheduling polyhedra
| Content Provider | Semantic Scholar |
|---|---|
| Author | Balas, E. Andrew |
| Copyright Year | 2015 |
| Abstract | A well-known job shop scheduling problem can be formulated as follows. Given a graph G with node set N and with directed and undirected arcs, find an orientation of the undirected arcs that minimizes the length of a longest path in G. We treat the problem as a disjunctive program, without recourse to integer variables, and give a partial characterization of the scheduling polyhedron P(N), i.e., the convex hull of feasible schedules. In particular, we derive all the facet inducing inequalities for the scheduling polyhedron P(K) defined on some clique with node set K, and give a sufficient condition for such inequalities to also induce facets of P(N). One of our results is that any inequality that induces a facet of P(H) for some HCK, also induces a facet of P(K). Another one is a recursive formula for deriving a facet inducing inequality with p positive coefficients from one with p-1 positive coefficients. We also address the constraint identification problem, and give a procedure for finding an inequality that cuts off a given solution to a subset of the constraints. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://repository.cmu.edu/cgi/viewcontent.cgi?article=1942&context=tepper |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
