Johnson's rule is a heuristic algorithm used to minimize the makespan in two-machine flowshop scheduling problems. It sequences tasks based on their processing times on two machines in non-decreasing order.
Example Code:
Here's a simplified Python example demonstrating Johnson's rule for assembly line scheduling:
def johnsons_rule(tasks):
tasks.sort(key=lambda x: min(x[0], x[1])) # Sort tasks by the minimum processing time
n = len(tasks)
sequence = []
i, j = 0, n - 1
while tasks:
if tasks[0][0] < tasks[0][1]:
sequence.append(tasks.pop(0))
else:
sequence.append(tasks.pop())
return sequence
# Example usage:
tasks = [(2, 3), (1, 4), (3, 5), (2, 6)] # Format: (processing time on machine 1, processing time on machine 2)
optimal_sequence = johnsons_rule(tasks)
print("Optimal Sequence:", optimal_sequence)
This code takes a list of tasks, where each task is represented as a tuple of processing times on two machines, and applies Johnson's rule to determine the optimal sequence of tasks.
