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

from qaekwy.engine import DirectEngine
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.specific import SpecificMinimum
from qaekwy.model.variable.branch import BranchIntegerVal
from qaekwy.model.variable.integer import IntegerVariable, IntegerExpressionVariable
from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType


class JobSchedulingProblem(Modeller):
    def __init__(self, processing_times, deadlines):
        super().__init__()

        num_jobs = len(processing_times)

        # Completion time variables
        completion_times = [
            IntegerVariable(
                var_name=f"completionTime_{i}", domain_low=0, domain_high=20,
                branch_val=BranchIntegerVal.VAL_MIN
            )
            for i in range(num_jobs)
        ]

        # Tardiness variables
        tardiness_vars = [
            IntegerVariable(
                var_name=f"tardiness_{i}", domain_low=0, domain_high=20,
                branch_val=BranchIntegerVal.VAL_MIN
            )
            for i in range(num_jobs)
        ]

        # Enforce sequential processing on a single machine
        # Job 0 finishes at its processing time
        self.add_constraint(RelationalExpression(completion_times[0] == processing_times[0]))

        # Each next job completes after the previous one
        for i in range(1, num_jobs):
            self.add_constraint(
                RelationalExpression(
                    completion_times[i] == completion_times[i-1] + processing_times[i]
                )
            )

        # Tardiness constraints
        for i in range(num_jobs):
            self.add_constraint(
                RelationalExpression(
                    tardiness_vars[i] >= completion_times[i] - deadlines[i]
                )
            )
            self.add_constraint(RelationalExpression(tardiness_vars[i] >= 0))

        # Total tardiness
        total_tardiness = IntegerExpressionVariable(
            var_name="total_tardiness",
            expression=sum(tardiness_vars),
            branch_val=BranchIntegerVal.VAL_MIN
        )

        # Add everything
        for v in completion_times + tardiness_vars + [total_tardiness]:
            self.add_variable(v)

        # Objective: Minimize total tardiness
        self.add_objective(SpecificMinimum(total_tardiness))

        # Use Branch-and-Bound search
        self.set_searcher(SearcherType.BAB)


if __name__ == "__main__":
    # Engine
    qaekwy_engine = DirectEngine()

    # Example data
    processing_times = [2, 3, 4, 1, 5]
    deadlines = [4, 7, 8, 5, 10]

    # Model
    job_scheduling_problem = JobSchedulingProblem(processing_times, deadlines)

    # Solve
    response = qaekwy_engine.model(model=job_scheduling_problem)
    solutions = response.get_solutions()
    solution = solutions[0]  # best solution

    # Print results
    for i in range(len(processing_times)):
        completion = solution[f"completionTime_{i}"]
        tardiness = solution[f"tardiness_{i}"]
        print(f"Job {i+1}: Completion Time = {completion}, Tardiness = {tardiness}")

    print(f"Total tardiness: {solution.total_tardiness}")

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