In the following paper http://nvlpubs.nist.gov/nistpubs/jres/111/2/V111.N02.A05.pdf a two objective model is developed. The usual way I see such models implemented is by adding weights in some linear fashion, e.g.:
Here a somewhat unusual form is used:
Indeed when β=0 we get a single objective scheduling problem:
Here the slack zk in bin k is maximized using a quadratic objective. This is not a trivial problem to solve in itself as the problem is non-convex and we need a global solver. The authors use Lingo but other suitable solvers are Baron and GloMiQo. (Looking at the data – all integer – it should not be too difficult to linearize this at the expense of extra binary variables).
When we look at the 2-objective problem formulation we can observe this can be written as:
When β is fixed the last term is constant, so we are left with:
Note that the paper want to maximize the slacks zk, but minimize the start time xi,ktk. I did not immediately understand how this objective can actually work. The more direct approach I would use is:
or may be:
Actually what is proposed in the paper is quite clever. Observe that minimizing the tksixi,k's is equivalent to maximizing tkzk (as the z is a slack indicating unused capacity).
The paper indicates it finds three different solutions. They probably use a scheme trying beta=0,0.01,0.02,.., or may be some bisection. There is a much better approach where we solve a single problem for each non-dominated point (plus one problem to detect there are no more such points). Using the separable formulation with:
we can add some equations that allow us to trace the efficient frontier. This actually gives us 4 non-dominated solutions:
The second solution was not found in the paper.
For a second data set the paper reports 8 different solutions. My model generates 18 non-dominated solutions:
My conclusion: although the proposed formulation is quite clever, a more traditional formulation allows us to better trace the efficient frontier.