Branch and cut for single machine scheduling.

摘要

We study the problem of finding a schedule for several jobs on a single machine, called single machine scheduling (SMS). Our focus is on the branch-and-cut approach (B&C). During the last 20 years, B&C has accumulated an astonishing record of solving difficult combinatorial optimization problems in practice, and as a result, it is today a standard tool for solving such problems. It is also widely available through academic and commercial software. On the other hand, SMS stands as a problem for which B&C, with its present tools, has not been successful. Here we present our contribution to B&C for SMS. We first study robust SMS. Next we study deterministic SMS with release dates and deadlines. Finally, we study SMS with sequence dependent setup times. We consider two different ways of formulating SMS. First, the traditional mixed-integer programming (MIP) approach, which introduces auxiliary binary variables to the model to formulate the combinatorial constraints of the problem. Second, B&C without auxiliary binary variables, which dispenses with the use of the auxiliary binary variables and enforces the combinatorial constraints directly in the B&C algorithm through specialized branching and cutting planes. In this case, the only variables in the model are the (continuous) starting (or completion) time variables. We investigate the polyhedra of these models. Our ultimate goal is to obtain families of strong cutting planes that will strengthen the SMS model through B&C. We present computational results that demonstrate the effectiveness of our theory. At the end, we present further directions of research.