A relaxed version of job shop scheduling

Question

I am working on a formulation for a problem that seems similar to the bin packing problem. My problem variables include items that are to be placed in bins, special events that are conditionally required, and the bins themselves. The constraints include

1. Capacity constraints for the bins

2. Certain items cannot be in the same bin as other items

3. Certain items must be have a special event between them. For example, to get from item i to item j, a special event must occur. Based on certain properties of the item.

4. A sequence dependent constraint such that items must follow a particular order in the bins. For example, item i must come before items j,k (if they are in the same bin together) and therefore cannot be placed in the bin after them. This is determined by a property of the item.

The objective for this problem is to identify the least number of bins needed to store all of the items, with an upper bound on the number of special events allowed on a bin.

The most obvious formulation I can think of is to have binary variables x_ijk and y_ijk. Where index i is the item (or special event taking place), j is the bin, and k is the position on the bin. Using a triple index like this makes formulating the problem quite simple, but I believe for even a modest size (100 items), the problem size is massive. I expect encoding the variables this way will make the problem size large because I am after a feasible solution and therefore expect the number of items = number of bins = number of sequence position. This guarantees the edge cases of all items being placed on a single bin, and all items being associated to their own individual bins.

Is there another formulation that is more efficient that can be used to model this problem?

Answer 1

I recommend using binary item-to-bin assignment variables $x_{i,b}$ and continuous nonnegative start time variables $s_i$. You can think of each item as having duration $1$ so that precedence constraints look like $s_i+1\le s_j$ if item $i$ must precede item $j$ and items $i$ and $j$ are assigned to the same bin. You can enforce this as follows: \begin{align} x_{i,b} + x_{j,b} - 1 &\le y_{i,j} \tag1 \\ s_i + 1 - s_j &\le M_{i,j}(1-y_{i,j}) \tag2 \\ \end{align} Constraint $(1)$ enforces $x_{i,b} \land x_{j,b} \implies y_{i,j}$. Constraint $(2)$ enforces $y_{i,j} \implies s_i+1\le s_j$.

Answer 2

Such a problem is difficult to model and solve following a MILP approach as suggested above. Indeed, the resulting MILP instances will grow quadratically regarding the number of items and bins, while the linear relaxation will be weak.

Your problem is closer to a job shop scheduling problem than a basic bin packing problem because of your temporal constraints between items. It can be modeled compactly by following a list-based modeling approach instead of the classical Boolean modeling approach as proposed above. This is a modeling approach offered by LocalSolver, which is different from traditional MILP solvers. Note that LocalSolver is commercial software. Nevertheless, it is free for faculty and students.

Below is the code snippet to model the job shop scheduling problem by using the LocalSolver modeling language, namely LSP:

function model() {
  // Integer decisions: start time of each activity
  // start[j][m] is the start time of the activity of job j which is processed on machine m
  start[j in 0..nbJobs-1][m in 0..nbMachines-1] <- int(0, maxStart);
  end[j in 0..nbJobs-1][m in 0..nbMachines-1] <- start[j][m] + processingTime[j][m];

  // Precedence constraints between the activities of a job
  for [j in 0..nbJobs-1][k in 1..nbMachines-1]
    constraint start[j][machineOrder[j][k]] >= end[j][machineOrder[j][k-1]];

  // Sequence of activities on each machine
  jobsOrder[m in 0..nbMachines-1] <- list(nbJobs);

  for [m in 0..nbMachines-1] {
    // Each job has an activity scheduled on each machine
    constraint count(jobsOrder[m]) == nbJobs;

    // Disjunctive resource constraints between the activities on a machine
    constraint and(0..nbJobs-2, i => start[jobsOrder[m][i+1]][m] >= end[jobsOrder[m][i]][m]);
  }

  // Minimize the makespan: end of the last activity of the last job
  makespan <- max[j in 0..nbJobs-1] (end[j][machineOrder[j][nbMachines-1]]);
  minimize makespan;
}

You can write the same model in Python, Java, C#, or C++. Just have a look at the job shop scheduling example here.

Having followed this modeling approach, LocalSolver finds quality solutions in minutes on a standard computer for instances with thousands of jobs to schedule. LocalSolver embeds and combines neighborhood search, constraint programming, and mixed-integer linear programming techniques under the hood to get such results.