Objectives¶

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 have different due dates (12 and 1, respectively). 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);

Let’s solve this model and inspect the results.

[2]:

result = model.solve(display=False)
print(result)

Solution results
================
  objective: 2.00
lower bound: 2.00
     status: Optimal
    runtime: 0.01 seconds

[3]:

for idx, job in enumerate(result.best.jobs):
    start, end = job.start, job.end
    print(f"Job {idx}: start={job.start}, end={job.end}")

Job 0: start=0, end=1
Job 1: start=1, end=2

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

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.

[4]:

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

Solution results
================
  objective: 0.00
lower bound: 0.00
     status: Optimal
    runtime: 0.00 seconds

[5]:

print(f"Makespan = {result.best.makespan}")
print(f"Total tardiness = {result.best.total_tardiness}")

for idx, job in enumerate(result.best.jobs):
    start, end, tardiness = job.start, job.end, job.tardiness
    print(f"Job {idx}: start={start}, end={end}, tardiness={tardiness}")

Makespan = 12
Total tardiness = 0
Job 0: start=11, end=12, tardiness=0
Job 1: start=0, end=1, tardiness=0

This time, the solver chooses to start with the second job to meet its due date precisely. The setup time is taken for granted, and the due date of the first job is also met. This leads to no tardiness for both jobs, 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.

[6]:

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

Solution results
================
  objective: 4.00
lower bound: 4.00
     status: Optimal
    runtime: 0.00 seconds

[7]:

print(f"Makespan = {result.best.makespan}")
print(f"Total tardiness = {result.best.total_tardiness}")

for idx, job in enumerate(result.best.jobs):
    start, end, tardiness = job.start, job.end, job.tardiness
    print(f"Job {idx}: start={start}, end={end}, tardiness={tardiness}")

Makespan = 2
Total tardiness = 1
Job 0: start=0, end=1, tardiness=0
Job 1: start=1, end=2, tardiness=1

Here, the total tardiness is twice as important as the makespan. As a result, the solver starts with the first job 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. The first job is three times as important as the second job in this example.

[8]:

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);

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

[9]:

result = model.solve(display=False)
print(result)

Solution results
================
  objective: 2.00
lower bound: 2.00
     status: Optimal
    runtime: 0.00 seconds

[10]:

print(f"Makespan = {result.best.makespan}")
print(f"Total tardiness = {result.best.total_tardiness}")

for idx, job in enumerate(result.best.jobs):
    start, end, tardiness = job.start, job.end, job.tardiness
    print(f"Job {idx}: start={start}, end={end}, tardiness={tardiness}")

Makespan = 3
Total tardiness = 2
Job 0: start=0, end=2, tardiness=0
Job 1: start=2, end=3, 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 maximum weighted tardiness of all jobs.

• 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) + w_{\text{max tard.}} \cdot \max_{j} \left( w_j \cdot \text{tardiness}(j, s) \right) + \sum_{\text{obj} \neq \text{makespan}, \text{TST}, \text{max tard.}} 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.