Force gaps between tasks, tasks are scheduled within their job's time windows in Jobshop problem

Question

The problem I'm trying to solve is a modification of the original Jobshop problem. The additional constraints are:

1. There is only one machine for all jobs and their tasks.
2. Each job has a priority (integer value, greater value means greater priority). Tasks of a higher-priority job should be considered first.
3. Tasks of a given job have same duration, for example: job_1 has 3 tasks and all of its tasks have duration of 5; job_2 has 2 tasks and all of its tasks have duration of 7, etc.
4. Each job has time windows (integer values), within which its tasks must be scheduled, for example: 0 - 10, 5 - 30, etc. Windows timestamps of all jobs may overlap.
5. All tasks are optional, this means that if there is no space for job's task within given job's window, algorithm should consider another window of the given job (if another window is present) and try to schedule this task within that another window.
6. Tasks of all jobs must not overlap (machine can process only one task at a time).
7. There must be a gap between tasks of each job (integer value; gap size depends on the job). Tasks of other jobs may be scheduled within this gap if it has enough space for them.

The objective is to schedule as many tasks of higher-priority jobs as possible. The problem I cannot cope with is that tasks do not have gaps between them. The reason for this IMO is that tasks are not always scheduled successively, because I define constraints only between successive tasks. For example: currently, the constraint formula for gaps between each task is defined like this: job_tasks[taskID + 1].start >= job_tasks[taskID].end + jobs_gaps[jobID]. This would work if the tasks are scheduled successively: task_1 -> task_2 -> task_3. But if tasks are scheduled not successively, say: task_1 -> task_3 -> task_2, then the constraints are not forced between pairs task_1 -> task_3 and task_3 -> task_2 because they only apply to the neighboring tasks, according to the formula.

I also use 3D array x to indicate that task with taskID of job with jobID is scheduled within window of windowID; this idea is taken from Multiple Knapsack problem.

The full program code is shown below:

public class MinimalJobshopSat {
    public static void main(String[] args) {
        Loader.loadNativeLibraries();
        // [START data]
        class Task {
            int duration;

            public Task(int duration) {
                this.duration = duration;
            }
        }
        class TaskType {
            IntVar start;
            IntVar end;
            IntervalVar interval;
        }

        final List<List<Task>> allJobs = Arrays.asList(
                Arrays.asList(new Task(3), new Task(3), new Task(3), new Task(3)), // Job0
                Arrays.asList(new Task(5), new Task(5), new Task(5), new Task(5)), // Job1
                Arrays.asList(new Task(10), new Task(10),new Task(10), new Task(10)) // Job2
        );

        final int[] priorities = {9, 5, 3};

        int numMachines = 1;
        final int[] allMachines = IntStream.range(0, numMachines).toArray();

        int horizon = 1_000_000;

        final int[][] windowsStarts = {
                {0, 30}, // windows starts for job 0
                {50}, // windows starts for job 1
                {100}
        };
        final int[][] windowsEnds = {
                {20, 40}, // windows ends for job 0
                {70}, // windows ends for job 1
                {120}
        };
        final int[] jobsBuffers = {5, 10, 15};
        // [END data]

        // Creates the model.
        // [START model]
        CpModel model = new CpModel();
        // [END model]

        // [START variables]
        Map<List<Integer>, TaskType> allTasks = new HashMap<>();
        List<IntervalVar> machineIntervals = new ArrayList<>();

//        x[jobID][taskID][windowID] = 1 if task with 'taskID' of a job with 'jobID' is assigned to a window with 'windowID'
        List<List<List<Literal>>> x = new ArrayList<>();
        for (int jobID = 0; jobID < allJobs.size(); ++jobID) { // for each job
            final List<List<Literal>> jobLiterals = new ArrayList<>();

            for (int taskID = 0; taskID < allJobs.get(jobID).size(); ++taskID) { // for each job's task
                final List<Literal> taskLiterals = new ArrayList<>();

                for (int windowID = 0; windowID < windowsStarts[jobID].length; ++windowID) { // for each job's window
                    taskLiterals.add(model.newBoolVar("x_" + jobID + "_" + taskID + "_" + windowID));
                }

                jobLiterals.add(taskLiterals);
            }

            x.add(jobLiterals);
        }

        for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
            List<Task> job = allJobs.get(jobID);
            final int firstWindowStart = Arrays.stream(windowsStarts[jobID]).min().getAsInt(); // job's makespan start
            final int lastWindowEnd = Arrays.stream(windowsEnds[jobID]).max().getAsInt(); // job's makespan end

            for (int taskID = 0; taskID < job.size(); ++taskID) {
                Task task = job.get(taskID);
                TaskType taskType = new TaskType();

                for (int windowID = 0; windowID < windowsStarts[jobID].length; ++windowID) {
                    String suffix = "_" + jobID + "_" + taskID + "_" + windowID;

                    Literal literal = x.get(jobID).get(taskID).get(windowID);
                    taskType.start = model.newIntVar(firstWindowStart, lastWindowEnd, "start" + suffix);
                    taskType.end = model.newIntVar(firstWindowStart, lastWindowEnd, "end" + suffix);
                    taskType.interval = model.newOptionalIntervalVar(
                            taskType.start,
                            model.newConstant(task.duration),
                            taskType.end,
                            literal,
                            "interval" + suffix
                    );

//                    task must be within window if x[jobID][taskID][windowID] is true
                    model.addGreaterOrEqual(taskType.start, model.newConstant(windowsStarts[jobID][windowID])).onlyEnforceIf(literal);
                    model.addLessOrEqual(taskType.end, model.newConstant(windowsEnds[jobID][windowID])).onlyEnforceIf(literal);

                    List<Integer> key = Arrays.asList(jobID, taskID, windowID);
                    allTasks.put(key, taskType);
                    machineIntervals.add(taskType.interval);
                }

            }
        }
        // [END variables]

        // [START constraints]
        // Create and add disjunctive constraints. Tasks of all jobs must not overlap.
        model.addNoOverlap(machineIntervals);

        // Precedences inside a job.
        for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
            List<Task> job = allJobs.get(jobID);
            for (int taskID = 0; taskID < job.size() - 1; ++taskID) {
                for (int windowID = 0; windowID < windowsStarts[jobID].length; ++windowID) {
                    List<Integer> prevKey = Arrays.asList(jobID, taskID, windowID);
                    List<Integer> nextKey = Arrays.asList(jobID, taskID + 1, windowID);

//                Tasks of given job must be successive
                    model.addGreaterOrEqual(allTasks.get(nextKey).start, LinearExpr.sum(new LinearArgument[] {
                            allTasks.get(prevKey).end, model.newConstant(jobsBuffers[jobID])
                    }));
                }

            }
        }
        // [END constraints]

        // [START objective]
        // Makespan objective.
        IntVar objVar = model.newIntVar(0, horizon, "makespan");
        List<IntVar> ends = new ArrayList<>();
        for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
            List<Task> job = allJobs.get(jobID);
            for (int windowID = 0; windowID < windowsStarts[jobID].length; ++windowID) {
                List<Integer> key = Arrays.asList(jobID, job.size() - 1, windowID);
                ends.add(allTasks.get(key).end);
            }
        }
        model.addMaxEquality(objVar, ends);
        model.minimize(objVar);
        // [END objective]

        // Creates a solver and solves the model.
        // [START solve]
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.solve(model);
        // [END solve]

        // [START print_solution]
        if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
            class AssignedTask {
                int jobID;
                int taskID;
                int start;
                int duration;
                int windowID;
                // Ctor

                public AssignedTask(int jobID, int taskID, int start, int duration, int windowID) {
                    this.jobID = jobID;
                    this.taskID = taskID;
                    this.start = start;
                    this.duration = duration;
                    this.windowID = windowID;
                }
            }
            class SortTasks implements Comparator<AssignedTask> {
                @Override
                public int compare(AssignedTask a, AssignedTask b) {
                    if (a.start != b.start) {
                        return a.start - b.start;
                    } else {
                        return a.duration - b.duration;
                    }
                }
            }
            System.out.println("Solution:");
            // Create one list of assigned tasks per machine.
            List<AssignedTask> assignedJobs = new ArrayList<>();
            for (int jobID = 0; jobID < allJobs.size(); ++jobID) {
                List<Task> job = allJobs.get(jobID);
                for (int taskID = 0; taskID < job.size(); ++taskID) {
                    Task task = job.get(taskID);

                    for (int windowID = 0; windowID < windowsStarts[jobID].length; ++windowID) {
                        List<Integer> key = Arrays.asList(jobID, taskID, windowID);
                        AssignedTask assignedTask = new AssignedTask(
                                jobID, taskID, (int) solver.value(allTasks.get(key).start), task.duration, windowID);
                        assignedJobs.add(assignedTask);
                    }
                }
            }

            // Create per machine output lines.
            String output = "";
            for (int machine : allMachines) {
                // Sort by starting time.
                Collections.sort(assignedJobs, new SortTasks());
                String solLineTasks = "Machine " + machine + ": ";
                String solLine = "           ";

                for (AssignedTask assignedTask : assignedJobs) {
                    String name = "job_" + assignedTask.jobID + "_task_" + assignedTask.taskID + "_win_" + assignedTask.windowID;
                    // Add spaces to output to align columns.
                    solLineTasks += String.format("%-22s", name);

                    String solTmp =
                            "[" + assignedTask.start + "," + (assignedTask.start + assignedTask.duration) + "]";
                    // Add spaces to output to align columns.
                    solLine += String.format("%-22s", solTmp);
                }
                output += solLineTasks + "%n";
                output += solLine + "%n";
            }
            System.out.printf("Optimal Schedule Length: %f%n", solver.objectiveValue());
            System.out.printf(output);
        } else {
            System.out.println("No solution found.");
        }
        // [END print_solution]

        // Statistics.
        // [START statistics]
        System.out.println("Statistics");
        System.out.printf("  conflicts: %d%n", solver.numConflicts());
        System.out.printf("  branches : %d%n", solver.numBranches());
        System.out.printf("  wall time: %f s%n", solver.wallTime());
        // [END statistics]
    }

    private MinimalJobshopSat() {}
}

Do you know a way/conception to force tasks to have gaps? Thank you for the answers.

Edit: I've updated allTasks key to also include windowID, and after that some tasks of jobs started to duplicate for some reason.

Cross-reference to the same question: Discord of OR-Tools

Answer 1

Here is a working version of your code:

• You need to change the objective. The obvious optimal is not to schedule any job.
• You need to add a 0 -> 0 arc to support no schedule jobs.
• I use model.AddImplication() for clarity
• ends are really not defined for unperformed intervals. I replaced the Max() by a set of enforced precedences.
• Furthermore, I force start[i] to be equal to release_dates[i] if the job is not scheduled.

from ortools.sat.python import cp_model


# ----------------------------------------------------------------------------
# Model.
model = cp_model.CpModel()

# ----------------------------------------------------------------------------
# Data.
job_durations = [
    1, 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 5
]

release_dates = [
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
]

due_dates = [
    0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1
]

# ----------------------------------------------------------------------------
# Helper data.
num_jobs = len(job_durations)
all_jobs = range(num_jobs)

# True is job of 'job_id' is scheduled, false otherwise.
x = [model.NewBoolVar(f'x_{job_id}') for job_id in all_jobs]

# ----------------------------------------------------------------------------
# Set big enough horizon value.
horizon = sum(job_durations) + max(due_dates)
print('Horizon =', horizon)

# ----------------------------------------------------------------------------
# Global storage of variables.
intervals = []
starts = []
ends = []

# ----------------------------------------------------------------------------
# Scan the jobs and create the relevant variables and intervals.
for job_id in all_jobs:
    duration = job_durations[job_id]
    release_date = release_dates[job_id]
    due_date = due_dates[job_id] if due_dates[job_id] != -1 else horizon
    print('job %2i: start = %5i, duration = %4i, end = %6i' %
          (job_id, release_date, duration, due_date))
    name_suffix = '_%i' % job_id
    start = model.NewIntVar(release_date, due_date, 's' + name_suffix)
    end = model.NewIntVar(release_date, due_date, 'e' + name_suffix)
    interval = model.NewOptionalIntervalVar(start, duration, end, x[job_id], 'i' + name_suffix)
    starts.append(start)
    ends.append(end)
    intervals.append(interval)

# No overlap constraint.
model.AddNoOverlap(intervals)

# ----------------------------------------------------------------------------
# Transition times using a circuit constraint.
arcs = []

# No job scheduled.
empty_lit = model.NewBoolVar('empty_lit')
arcs.append([0, 0, empty_lit])

for i in all_jobs:
    # Initial arc from the dummy node (0) to a job.
    start_lit = model.NewBoolVar('')
    arcs.append([0, i + 1, start_lit])

    # If this job is the first, set to minimum starting time.
    model.Add(starts[i] == release_dates[i]).OnlyEnforceIf(start_lit)

    # Job is scheduled if the graph starts with it.
    model.AddImplication(start_lit, x[i])

    # Final arc from an arc to the dummy node.
    arcs.append([i + 1, 0, model.NewBoolVar('')])

    # Add 'x[job_id].Not()' literal to each node
    arcs.append([i + 1, i + 1, x[i].Not()])

    # Link empty_lit and x[i]
    model.AddImplication(empty_lit, x[i].Not())

    # Fix start and end for unperformed jobs.
    model.Add(start[i] == release_dates[i]).OnlyEnforceIf(x[i].Not())

    for j in all_jobs:
        if i == j:
            continue

        lit = model.NewBoolVar('%i follows %i' % (j, i))
        arcs.append([i + 1, j + 1, lit])

        model.Add(starts[j] >= ends[i]).OnlyEnforceIf(lit)

        # job[i] and job[j] are scheduled if they are successively scheduled by the solver.
        model.AddImplication(lit, x[i])
        model.AddImplication(lit, x[j])


model.AddCircuit(arcs)

# ----------------------------------------------------------------------------
# Objective.
makespan = model.NewIntVar(0, horizon, 'makespan')
for i in all_jobs:
    model.Add(makespan >= ends[i]).OnlyEnforceIf(x[i])
model.Minimize(makespan)

# ----------------------------------------------------------------------------
# Solve.
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 60 * 60 * 2
solver.parameters.num_search_workers = 16
solver.Solve(model)
print(solver.ResponseStats())
for job_id in all_jobs:
    if solver.BooleanValue(x[job_id]):
        print(
            f'job {job_id} starts at {solver.Value(starts[job_id])} and ends at {solver.Value(ends[job_id])}'
        )
    else:
        print(f'job {job_id} is not scheduled')