The following model tries to assign jobs to ‘bins’ (bins can be interpreted as workstations) in such a way that the remaining space in the bins is as large as possible (i.e. as little fragmentation as possible so that we have capacity left for large jobs).
Essentially we place high value on large values on remaining capacity zk. We consider here cases with β=0 (if β>0 we also like jobs to be executed early: remaining capacity more in the future is more valuable). This is a non-convex problem so not so easy to solve. This is also the model discussed here.
The choice of a quadratic objective is somewhat arbitrary. It is a simple function that has the required properties that larger values for zk are valued more than proportionally (i.e. linear). In practice I often handle this by some piecewise linear formulation. In addition in practical cases it may be useful to give bins (workstations) without any jobs additional value (no set-up or clean-up in this case, so an unused bin may be preferred).
With Cplex’s global MIQP solver (http://www.orsj.or.jp/ramp/2014/paper/4-3.pdf) we have now at least three ways to solve this problem with Cplex:(global MIQP, MIP with SOS2 interpolation, MIP with binaries exploiting integer data for capacity and job spans). Using an expanded (larger) version of the dataset provided in the paper with 27 bins and 15 jobs to allocate we try a few formulations.
- The global MIQP formulation uses the above model directly. We solve to optimality with 4 threads. Cplex selects this algorithm with option SolutionTarget=3.
- We can add a small value for β to try to reduce some symmetry in the model. We are still aiming for large remaining capacities, but we add a little bit of noise to distinguish similar solutions. The purpose is not really to add a ‘schedule as early as possible’ objective but rather just to increase the performance of the branch-and-bound algorithm. In the experiment we use β=0.01. Note: this may not always give us the same optimal solution.
- We can use a piecewise linear formulation using SOS2 variables. In this case we used 4 segments. Obviously this is an approximation, so we may arrive at a different optimal solution. However in this case just using 4 segments is good enough to find the global optimum.
- We can assume all capacity and job length data is integer (as is the case for the example data sets in the paper), and use this to formulate a linear model with extra binary variables. Essentially we implement a table lookup. If all data is integer valued (and the range of the numbers is not outrageously large) this will give us the proven optimal solution of the original MIQP. Exploiting properties of the input data can be key to solve things fast.
Here are the results:
These results confirm my experience. I typically use a piecewise linear formulation with just a few segments for this. In most cases I use even fewer than the 4 segments we used here. This seems often to perform reasonably well.
The authors of the original paper did not explore these alternatives but concluded quickly the global MIQP (implemented in Lingo) was too slow and implemented a heuristic. I am not sure if they would have done the same if they saw these results.
Update:
Instead of somewhat more complex formulations suggested in the comments, a simple table look-up using binary variables can be implemented with three constraints having a SOS1 structure:
This will make sure we have y=f(x) where x = 0,1,…,n. This is very close to the SOS2 formulation so took me just minutes to implement.
>> MIP with binaries exploiting integer data for capacity and job spans
ReplyDeleteThere are (at least) two ways to do this: using that z_k can take any integer value between 0 and N := max_k cap_k:
1. using binary variables y_{ik} that take the value 1 only if z_k = i. The objective becomes sum_k sum_i i^2 y_{ik}; the extra constraints are 1 - y_{ik} >= (i - z_k)/N and 1 - y_{ik} >= (z_k - i)/N.
2. using binary variables y_{ik} that sum to z_k. The expression (sum_i y_{ik})^2 contains products of binary variables, which can be linearized in an exact reformulation.
Both have a weak LP relaxation; the first because it is a big-M formulation, the second because for each k, all y_{ik} are symmetric and you may need to fix many values before it has any effect on the solution.
One more thought: the maximum of a concave function over a convex set is attained at an extreme point of the feasible set. You therefore do not need to specify x_{jk} as binary. It will be interesting to see how this affects the running time of all methods.
ReplyDeleteI wish I could edit my message, it's either "the maximum of a convex function over a convex set" or "the minimum of a concave function over a convex set".
ReplyDelete