Job Scheduling Problem

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.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_times = [
            IntegerVariable(
                var_name=f"completionTime_{i}", domain_low=0, domain_high=100
            )
            for i in range(num_jobs)
        ]

        # Constraint: Completion time of each job is after its processing time
        for i in range(num_jobs):
            self.add_constraint(
                RelationalExpression(completion_times[i] >= processing_times[i])
            )

        # Objective: Minimize total tardiness
        total_tardiness = IntegerExpressionVariable(
            var_name="total_tardiness",
            expression=sum(
                max(0, completion_times[i] - deadlines[i]) for i in range(num_jobs)
            ),
        )

        self.add_variable(total_tardiness)
        self.add_objective(SpecificMinimum(total_tardiness))

        # Add variables and constraints to the problem
        for completion_time_var in completion_times:
            self.add_variable(completion_time_var)

        # Set the search strategy to Branch-and-bound Search (BAB)
        self.set_searcher(SearcherType.BAB)


if __name__ == "__main__":
    # Create a Qaekwy engine for direct interaction
    qaekwy_engine = DirectEngine()

    # Define the processing times and deadlines for jobs
    processing_times = [2, 3, 4, 1, 5]
    deadlines = [4, 7, 8, 5, 10]

    # Create the job scheduling problem instance
    job_scheduling_problem = JobSchedulingProblem(processing_times, deadlines)

    # Request the Qaekwy engine to solve the job scheduling problem
    response = qaekwy_engine.model(model=job_scheduling_problem)

    # Retrieve the list of solutions from the response
    list_of_solutions = response.get_solutions()
    solution = list_of_solutions[0]

    for solution_item, solution_value in solution.items():
        if "completionTime_" in solution_item:
            idx = int(solution_item.split("_")[1])
            tardiness = max(0, solution_value - deadlines[idx])
            print(
                f"Job {idx+1}: Completion Time = {solution_value}, Tardiness = {tardiness}"
            )
    print(f"Total tardiness: {solution.total_tardiness}")