Objectives in PyJobShop¶

If you’re using this notebook in Google Colab, be sure to install PyJobShop first by executing pip install pyjobshop in a cell.

This notebook provides an overview of the different objectives in PyJobShop via simple scheduling problems, specifically:

• How to set different objective weights using PyJobShop’s Model interface,

• How to set the job weights with Model,

• Giving an overview of the different objectives in PyJobShop,

• How the objective value of a schedule is calculated in PyJobShop.

For illustration, let’s add a single machine and some data to a PyJobShop Model. We add two jobs, each consisting of one task. The jobs’ due dates differ. Furthermore, switching from the second task to the first task has a setup time of 10 time units.

[1]:

from pyjobshop import Model

model = Model()
machine = model.add_machine()

jobs = [
    model.add_job(due_date=12),
    model.add_job(due_date=1),
]
tasks = [model.add_task(job=job) for job in jobs]
modes = [model.add_mode(task, machine, duration=1) for task in tasks]
model.add_setup_time(machine, tasks[1], tasks[0], 10)

[1]:

SetupTime(machine=0, task1=1, task2=0, duration=10)

Let’s solve this model and inspect the results.

[2]:

result = model.solve(display=False)

print("Solver status =", result.status)
print("Objective value =", result.objective)

for idx, task in enumerate(result.best.tasks):
    print(f"Task {idx} start time =", task.start)

Solver status = SolveStatus.OPTIMAL
Objective value = 2.0
Task 0 start time = 0
Task 1 start time = 1

By default, the makespan is minimized. The due dates are thus ignored. Consequently, it is best to avoid setup time and prioritize task one over task two.

Setting different objective weights¶

Now, let’s try to meet the due dates by setting the (weighted) total tardiness as an objective and solve it again.

[3]:

model.set_objective(weight_total_tardiness=1)  # all other weights are 0
result = model.solve(display=False)

print("Solver status =", result.status)
print("Objective value =", result.objective)
print("Makespan =", result.best.makespan)

for idx, task in enumerate(result.best.tasks):
    print(f"Task {idx} start time =", task.start)

Solver status = SolveStatus.OPTIMAL
Objective value = 0.0
Makespan = 12
Task 0 start time = 11
Task 1 start time = 0

This time, the solver chooses to start with task two to meet its due date precisely. The setup time is taken for granted, as also the due date of task one is met. This leads to 0 tardiness, but a makespan of 12.

Suppose you are interested in minimizing the weighted sum of the makespan and the total tardiness. All other weights are zero. You can set both objectives with different weights, as shown next.

[4]:

model.set_objective(weight_makespan=1, weight_total_tardiness=2)
result = model.solve(display=False)

print("Solver status =", result.status)
print("Objective value =", result.objective)
print("Makespan =", result.best.makespan)

for idx, task in enumerate(result.best.tasks):
    print(f"Task {idx} start time =", task.start)

Solver status = SolveStatus.OPTIMAL
Objective value = 4.0
Makespan = 2
Task 0 start time = 0
Task 1 start time = 1

Here, the total tardiness is twice as important as the makespan. As a result, the solver starts with task one again, leading to an objective value of 1 * 2 + 2 * 1 = 4 (weight_makespan * makespan + weight_total_tardiness * total_tardiness).

Different job weights¶

In practice, jobs can have different priorities. For example, you would like to meet the due date of a new customer to show your best service. To differentiate between the importance of jobs, you can set job weights as shown in the following single machine example with two jobs. Job one is three times as important as job two in this example.

[5]:

model = Model()

machine = model.add_machine()

jobs = [
    model.add_job(weight=3, due_date=2),
    model.add_job(weight=1, due_date=1),
]
tasks = [model.add_task(job=job) for job in jobs]
modes = [
    model.add_mode(tasks[0], machine, duration=2),
    model.add_mode(tasks[1], machine, duration=1),
]
model.set_objective(weight_total_tardiness=1)

[5]:

Objective(weight_makespan=0, weight_tardy_jobs=0, weight_total_flow_time=0, weight_total_tardiness=1, weight_total_earliness=0, weight_max_tardiness=0, weight_max_lateness=0, weight_total_setup_time=0)

When solving this model, the tardiness of job one counts three times as much as the tardiness of job two towards the weighted total tardiness. When the job weights were equal, it would be best to schedule job two first (giving a total tardiness of 1 from job one). However, because job one is three times as important, the solver chooses to start with job one, as shown in the following.

[6]:

result = model.solve(display=False)

print("Solver status =", result.status)
print("Objective value =", result.objective)

for idx, task in enumerate(result.best.tasks):
    tardiness = max(task.end - jobs[idx].due_date, 0)

    print(f"Task {idx} start time =", task.start)
    print(f"Task {idx} tardiness =", tardiness)

Solver status = SolveStatus.OPTIMAL
Objective value = 2.0
Task 0 start time = 0
Task 0 tardiness = 0
Task 1 start time = 2
Task 1 tardiness = 2

Other objectives in PyJobShop¶

PyJobShop supports the minimization of the weighted sum of the following objectives:

• Makespan: the finish time of the latest task.

• Number of tardy jobs: the weighted sum of all tardy jobs, where a job is tardy when it does not meet its due date.

• Total flow time: the weighted sum of the length of stay in the system of each job, from their release date to their completion.

• Total tardiness: the weighted sum of the tardiness of each job, where the tardiness of a job is the difference between its completion time and its due date, where tardiness is 0 when it is completed before its due date.

• Total earliness: the weighted sum of the earliness of each job, where the earliness of a job is the difference between its due date and its completion time, where earliness is 0 when its completion time is after its due date.

• Maximum tardiness: the weighted maximum tardiness of all jobs.

• Maximum lateness: the weighted maximum lateness of all jobs. The lateness of a job is the difference between its completion time and its due date (in contrast to tardiness, it can be smaller than 0).

• Total setup time: the sum of all sequence-dependent setup times between consecutive tasks on each machine.

The objective weights are captured in the Objective class; for more details, see its API documentation.

General calculation of a schedule’s objective value¶

We now explain how the objective value is calculated in general. To that end, let \(w_j\) denote the weight of job \(j\) and let \(w_{\text{obj}}\) denote the weight of objective \(\text{obj}\) (see the previous section for an overview of all objectives). We denote the contribution of job \(j\) to the objective \(\text{obj}\) in schedule \(s\) as \(\text{contribution}(j, \text{obj}, s)\). The value of the makespan of schedule \(s\) is denoted by \(\text{makespan}(s)\) and the value of the total setup time of schedule \(s\) is denoted by \(\text{TST}(s)\). The general objective value for schedule \(s\) is calculated in PyJobShop as follows: \begin{equation} \text{objective}(s) = w_{\text{makespan}} \cdot \text{makespan}(s) + w_{\text{TST}} \cdot \text{TST}(s) + \sum_{\text{obj} \neq \text{makespan}, \text{TST}} w_{\text{obj}} \cdot \sum_{j} w_j \cdot \text{contribution}(j, \text{obj}, s). \end{equation} The following simple example of two jobs, with given weights, release date, and start and end times, shows how the objective components are calculated and combined in the different objective values. In particular, the following table shows the objective component values for the two jobs.

Based on these objective component values, the following table shows the different objective values for the example.

Conclusion¶

This concludes the demonstration of the different objectives in PyJobShop. Using simple examples, we showed how to focus on different objectives and set their weights. Also, we showed how to set the weights of jobs to prioritize them. For more details about Objective, see the API documentation.