A common problem in production scheduling involves distributing jobs of varying durations across multiple identical machines to minimize the time when the last job finishes. In other words, the goal is to minimize the makespan.
Production Planning Problem Instances
The following list presents some instances of the makespan minimization problem. It involves a set number of identical machines and a set number of jobs that need to be assigned to these machines.
| Instance File Name | # Jobs | # Machines |
| PRODPLAN_M2_J5 | 5 | 2 |
| PRODPLAN_M2_J8 | 8 | 2 |
| PRODPLAN_M2_J21 | 21 | 2 |
| PRODPLAN_M4_J32 | 32 | 4 |
The order in which jobs are processed on a machine does not matter in this problem. Based on the required information, I’ve defined a human-readable file format and developed a generator to create additional test instances.
The following text file visualizes the structure of the production planning instance files:
NAME: PRODPLAN_M2_J5
TYPE: PRODPLAN_PROBLEM
COMMENT: Assign 5 jobs with given duration to 2 sequences processed on 2 (identic) machines (Leuthold)
NUM_MACHINES: 2
NUM_JOBS: 5
JOBS_ID_DURATION
1 1.8
2 8.6
3 7.8
4 2.9
5 5.2
EOFDesign A Construction Heuristic
Let’s consider how to distribute nnn jobs across mmm machines. Ideally, we want an assignment where all machines work for exactly the same amount of time to achieve optimal utilization and complete production as early as possible. However, this is rarely feasible due to varying job durations.
Given the differing job durations, a key question is whether to start with long-duration jobs or short ones. Starting with long jobs has the advantage of leaving shorter jobs to fill any remaining gaps at the end, potentially balancing machine usage more effectively.
A possible greedy heuristic approach could be the following:
- Sort the jobs in descending order by duration.
- Assign each job to the machine with the least current workload.
Implementation of the Construction Heuristic
We are now ready to translate the heuristic into program code. Based on the description above, this can be done directly with the help of ChatGPT.
The basic pattern of the heuristic can easily be sketched. One consideration remains regarding the storage of job assignments. I decided to use a list of lists for each machine, containing the job IDs of the jobs assigned to that machine.
A direct translation of our heuristic concept in python would look somewhat like this:
def production_greedy(num_machines, job_durations):
"""
construction heuristic to generate a fair solution to the production problem and distribute the jobs over the
(identical) machines in order to minimize overall production timespan. returns a dictionary with the machine-id as
key and the list of assigned job-ids.
it works as follows: all jobs are sorted by descending duration, then iteratively assigned to the machine having
the shortest production time so far.
:param num_machines: the number of (identical) machines which can process the jobs
:param job_durations: the durations of each job in a list
:return: a dictionary with the machine-id as key and the list of assigned job-ids.
"""
# Sort the jobs by duration in descending order
sorted_jobs = sorted(range(len(job_durations)), key=lambda x: job_durations[x], reverse=True)
# Initialize a list to keep track of jobs assigned to each machine
machine_jobs = [[] for _ in range(num_machines)]
# Initialize a list to keep track of the total duration on each machine
machine_loads = [0] * num_machines
# Assign jobs to machines
for job_id in sorted_jobs:
duration = job_durations[job_id]
# Find the machine with the minimum load
min_machine = min(range(num_machines), key=lambda x: machine_loads[x])
# Assign the job to this machine
machine_jobs[min_machine].append(job_id)
# Update the load of the machine
machine_loads[min_machine] += duration
return machine_jobs
That’s it! With this, we have a useful initial constructive heuristic. The remaining tasks are just to implement functions for reading and visualizing the data. The complete source code is available here.
Validation of the Implementation
As the final step, we should review the implementation to ensure it performs as expected. Visualizing the solutions can help, as graphical representation often makes it easier and faster to identify errors than simply examining the data.
| Instance File Name | # Jobs / # Machines | Description |
| PRODPLAN_M2_J4_test | 4 / 2 | Simple test instance to validate construction heuristic |
| PRODPLAN_M2_J5_test2 | 5 / 2 | Mean test instance test instance deliberately designed so that the heuristic doesn’t find optimum |
When testing heuristics, it’s useful to create simple test instances where the expected result is easy to define. The first instance is straightforward and can be solved to fully utilize both machines. The second instance is designed to exploit a weakness in the construction heuristic, preventing it from finding the optimal solution. The following plots visualize the solutions found:
Both results match our expectations, which gives us confidence that our implementation makes sense. When creating unit tests, the expectations can be directly formulated and checked with asserts. However, keep in mind that fixed checks for job assignments to specific machines depend on the implementation.
The complete source code is available here.