Job Scheduling

Example: Job Scheduling

Description

Let’s consider a scheduling problem, specifically the job scheduling problem. In this problem, you have a set of jobs, each with a processing time and a deadline. The goal is to schedule the jobs on a single machine to minimize the total tardiness, where tardiness is the amount of time a job is completed after its deadline. Let’s set up a simple job scheduling problem and solve it using Qaekwy.

The problem is approached by defining variables to represent the completion times of each job, constraints to ensure that the completion times are greater than or equal to the processing times, and an objective function to minimize the total tardiness.

Variables

In this Job Scheduling Problem model, integer variables are used to represent the completion times of each job. Each job corresponds to an integer variable, which represents the time when the job is completed.

Constraints

Completion Time Constraint: The completion time of each job must be greater than or equal to its processing time. This constraint ensures that a job cannot complete before it starts processing.

Objective

The objective of this Job Scheduling Problem is to minimize the total tardiness, which is calculated by summing the tardiness of each job. Tardiness is computed as the difference between the completion time of a job and its deadline, but only considering positive values.

The model is solved using the qaekwy optimization engine, and the solutions are retrieved from the response. For each solution, the scheduled jobs are printed along with their completion times and tardiness values. The total tardiness across all scheduled jobs is also calculated and displayed.

Code

import qaekwy as qw

def solve_job_scheduling(processing_times: list[int], deadlines: list[int]):
    # Initialisation
    m = qw.Model()

    num_jobs = len(processing_times)
    horizon_max = sum(processing_times)

    # Defining variables
    completion_times = [
        m.integer_variable(
            name=f"completionTime_{i}",
            domain=(0, horizon_max),
            branch_val=qw.BranchIntegerVal.VAL_MIN
        )
        for i in range(num_jobs)
    ]

    tardiness_vars = [
        m.integer_variable(
            name=f"tardiness_{i}",
            domain=(0, horizon_max),
            branch_val=qw.BranchIntegerVal.VAL_MIN
        )
        for i in range(num_jobs)
    ]

    # --- Ordering constraints ---

    # The first job finished after its processing time
    m.constraint(completion_times[0] == processing_times[0])

    # Sequencing on a single machine: each job finishes after the previous one
    for i in range(1, num_jobs):
        m.constraint(
            completion_times[i] == completion_times[i-1] + processing_times[i]
        )

    # Calculating the delay for each job: tardiness = max(0, completion - deadline)
    for i in range(num_jobs):
        m.constraint(tardiness_vars[i] >= completion_times[i] - deadlines[i])
        m.constraint(tardiness_vars[i] >= 0)

    # Target variable: Sum of delays
    total_tardiness = m.integer_variable(
        name="total_tardiness",
        expression=sum(tardiness_vars),
        branch_val=qw.BranchIntegerVal.VAL_MIN
    )

    # Objective: To minimize the total delay
    m.minimize(total_tardiness)

    # Solution research using Branch-and-Bound
    return m.solve_one(searcher="bab")


if __name__ == "__main__":

    # Data of the problem
    proc_times = [2, 3, 4, 1, 5]
    dead_lines = [4, 7, 8, 5, 10]

    solution = solve_job_scheduling(proc_times, dead_lines)

    if solution:
        for i in range(len(proc_times)):
            comp = solution[f"completionTime_{i}"]
            tard = solution[f"tardiness_{i}"]
            print(f"Job {i+1}: Completion Time = {comp}, Tardiness = {tard}")

        print(f"\nTotal tardiness: {solution.total_tardiness}")
    else:
        print("No solution.")

Results

When you run the above code, it will output the scheduled jobs along with their completion times and tardiness values, as well as the total tardiness across all scheduled jobs.

Job 1: Completion Time = 2, Tardiness = 0
Job 2: Completion Time = 5, Tardiness = 0
Job 3: Completion Time = 9, Tardiness = 1
Job 4: Completion Time = 10, Tardiness = 5
Job 5: Completion Time = 15, Tardiness = 5

Total tardiness: 11