Constructive Heuristics for Job Shop Scheduling Problem (JSSP)#

Problem#

The Job Shop Scheduling Problem (JSSP) is a classic scheduling problem where jobs must be processed on machines in specific orders.

Given: A set of jobs, each consisting of operations that must be processed on specific machines for fixed durations
Objective: Minimize the makespan (total completion time)
Constraints: Each machine can process one operation at a time, each job’s operations must be processed in order

Algorithm Design Task#

Constructive heuristics iteratively select the next operation to schedule from feasible operations.

Inputs: Current status (machine_status, job_status), feasible operations
Outputs: Selected operation (job_id, machine_id, processing_time)

Evaluation#

Dataset: 16 instances, 50 jobs, 10 machines
Fitness: Average makespan (minimized)

Template#

template_program = '''
from typing import Sequence, Tuple, TypedDict, TypeAlias

JobId: TypeAlias = int
MachineId: TypeAlias = int
Time: TypeAlias = int
ProcessingTime: TypeAlias = int
Operation: TypeAlias = Tuple[JobId, MachineId, ProcessingTime]

def determine_next_operation(
    current_status: CurrentStatus,
    feasible_operations: Sequence[Operation],
) -> Operation:
    """
    Choose one operation from `feasible_operations` to schedule next.

    Args:
        current_status: Dict with 'machine_status' and 'job_status'
        feasible_operations: List of (job_id, machine_id, processing_time)

    Returns:
        One Operation tuple from feasible_operations
    """
    return min(feasible_operations, key=lambda op: op[2])
'''

task_description = '''
Given jobs and machines, schedule jobs on machines to minimize the total makespan.
Design an algorithm to select the next operation in each step.
'''

Configuration Parameters#

Parameter	Description	Default
`timeout_seconds`	Maximum evaluation time	20
`n_instance`	Number of problem instances	16
`n_jobs`	Number of jobs	50
`n_machines`	Number of machines	10

Example Usage#

from llm4ad.task.optimization.jssp_construct import JSSPEvaluation

evaluator = JSSPEvaluation()

def determine_next_operation(current_status, feasible_operations):
    # Shortest processing time rule
    return min(feasible_operations, key=lambda op: op[2])

result = evaluator.evaluate_program('', determine_next_operation)

Constructive Heuristics for Job Shop Scheduling Problem (JSSP)

Contents