Polyhedral results for position based scheduling of chains on a single machine

Horváth, Markó and Kis, Tamás (2018) Polyhedral results for position based scheduling of chains on a single machine. Other. UNSPECIFIED. (Submitted)

Preview

Text positionbased.pdf Download (411kB) | Preview

Abstract

We consider a scheduling problem where a set of unit-time jobs have to be sequenced on a single machine without any idle times between the jobs. Preemption of processing is not allowed. The processing cost of a job is determined by the position in the sequence, i.e., for each job and each position, there is an associated weight, and one has to determine a sequence of jobs which minimizes the total weight incurred by the positions of the jobs. In addition, the ordering of the jobs must satisfy the given chain precedence constraints. In this paper we investigate the polyhedron associated with a special case of the problem where each chain has length two. We show that optimizing over this polyhedron is strongly NP-hard, however, we present a class of facet-defining inequalities along with a polynomial-time separation procedure. We generalize these results to the case of chains with lengths at most two. Finally, we present our computational results that show that separating these inequalities can significantly improve a linear programming based branch-and-bound procedure to solve the problem.

Actions (login required)

Edit Item