I need to fix a program with a backward scheduling logic that allows assigning tasks following the priority order in which they appear in the headers of the schedule_table columns.
Since this is a backward scheduling approach, the tasks should start being placed from the row of the "Deadline" column where the task to be scheduled is located. For example, if we start with "Task C," the tasks should be placed starting from row 13 upwards.
If it’s not possible to place the tasks because there are not enough rows upwards, the tasks should begin from a few rows below the "Deadline" to fit into the corresponding columns.
The roadmap table provides information about which column in the schedule_table (in this case ‘Machine 1’, ‘Machine 2’, ‘Machine 3’, or ‘Machine 4’) each task should be placed in. It also specifies the number of successive hours (rows) that should be left free to place the indicated tasks. Keep in mind that a free cell is one that still contains None.
Given the order in which the columns appear in the roadmap headers, you first need to ensure that all "Task C" instances are placed, then place all "Task A" instances, then all "Task B" instances, and finally, ensure all "Task D" instances are placed.
def find_task_row(table, task):
"""Finds the row where the highest-priority task is located in the 'Deadline' column"""
for i in range(len(table)-1, -1, -1):
if table[i][-1] == task:
return i
return None
def assign_task(schedule_table, roadmap, task, task_index):
"""Assigns a task in the schedule_table according to the roadmap starting from its deadline"""
# Find the row of the task's deadline
deadline_row = find_task_row(schedule_table, task)
if deadline_row is None:
print(f"Task {task} has no deadline in the table.")
return
# Get the task's machines and required consecutive rows from the roadmap
task_info = roadmap[task_index + 1]
# Try to place the task in reverse order, starting from the deadline row
for machine, hours_needed in task_info:
machine_col = schedule_table[0].index(machine)
# Start from the deadline row and move upwards
start_row = deadline_row
while start_row >= 0:
can_place = all(schedule_table[start_row - i][machine_col] is None
for i in range(hours_needed) if start_row - i >= 0)
if can_place:
# Place the task
for i in range(hours_needed):
schedule_table[start_row - i][machine_col] = task
break
start_row -= 1
# If not enough space upwards, move downwards
if start_row < 0:
start_row = deadline_row + 1
while start_row + hours_needed - 1 < len(schedule_table):
can_place = all(schedule_table[start_row + i][machine_col] is None
for i in range(hours_needed))
if can_place:
# Place the task
for i in range(hours_needed):
schedule_table[start_row + i][machine_col] = task
break
start_row += 1
Here the inputs:
# Data input given as a roadmap
roadmap = [
['Task C', 'Task A', 'Task B', 'Task D'],
[['Machine 4', 3], ['Machine 1', 2], ['Machine 3', 1], ['Machine 2', 2]],
[['Machine 1', 2], ['Machine 2', 4], ['Machine 2', 3], ['Machine 3', 3]],
[['Machine 3', 3], ['Machine 3', 3], ['Machine 4', 3], ['Machine 1', 4]],
[['Machine 2', 1], ['Machine 4', 1], ['Machine 1', 1], ['Machine 4', 1]]
]
# Initialization of the schedule table with the 'Deadline' for each task already indicated in the respective row in the last column
schedule_table = [
['Hour', 'Machine 1', 'Machine 2', 'Machine 3', 'Machine 4', 'Deadline'],
[1, None, None, None, None, None],
[2, None, None, None, None, None],
[3, None, None, None, None, None],
[4, None, None, None, None, None],
[5, None, None, None, None, None],
[6, None, None, None, None, None],
[7, None, None, None, None, None],
[8, None, None, None, None, None],
[9, None, None, None, None, None],
[10, None, None, None, None, None],
[11, None, None, None, None, 'Task C'],
[12, None, None, None, None, 'Task A'],
[13, None, None, None, None, 'Task B'],
[14, None, None, None, None, None],
[15, None, None, None, None, None],
[16, None, None, None, None, 'Task D'],
[17, None, None, None, None, None]
]
# Backward scheduling logic for task assignment
# Print the modified table
for row in schedule_table: print(row)
The correct output for this case should be:
['Hour', 'Machine 1', 'Machine 2', 'Machine 3', 'Machine 4', 'Deadline'],
[1, 'Task A', 'Task D', None, None, None],
[2, 'Task A', 'Task D', None, None, None],
[3, None, 'Task A', 'Task D', 'Task C', None],
[4, None, 'Task A', 'Task D', 'Task C', None],
[5, None, 'Task A', 'Task D', 'Task C', None],
[6, 'Task C', 'Task A', 'Task B', None, None],
[7, 'Task C', 'Task B', None, 'Task A', None],
[8, None, 'Task B', 'Task C', None, None],
[9, 'Task D', 'Task B', 'Task C', None, None],
[10, 'Task D', None, 'Task C', 'Task B', None],
[11, 'Task D', 'Task C', 'Task A', 'Task B', 'Task C'],
[12, 'Task D', None, 'Task A', 'Task B', 'Task A'],
[13, 'Task B', None, 'Task A', None, 'Task B'],
[14, None, None, None, 'Task A', None],
[15, None, None, None, None, None],
[16, None, None, None, 'Task D', 'Task D'],
[17, None, None, None, None, None]
Note that there are cases like "Task A" where the assignments might not fit, and we need to start from 2 rows earlier than the "Deadline" row of "Task A."
schedule_table = [
['Hour', 'Machine 1', 'Machine 2', 'Machine 3', 'Machine 4', 'Deadline'],
[1, None, "Task A", None, None, None],
[2, None, "Task A", None, None, None],
[3, None, "Task A", None, "Task C", None],
[4, None, "Task A", None, "Task C", None],
[5, None, None, "Task A", "Task C", None],
[6, "Task C", None, "Task A", None, None],
[7, "Task C", None, "Task A", None, None],
[8, None, None, "Task C", None, None],
[9, None, None, "Task C", None, None],
[10, None, None, "Task C", None, None],
[11, None, "Task C", None, None, 'Task C'],
[12, None, None, None, "Task A", 'Task A'],
[13, None, None, None, None, 'Task B'],
[14, None, None, None, None, None],
[15, None, None, None, None, None],
[16, None, None, None, None, 'Task D'],
[17, None, None, None, None, None]
]
And after starting 2 rows earlier, it can place all the "Task A" instances:
schedule_table = [
['Hour', 'Machine 1', 'Machine 2', 'Machine 3', 'Machine 4', 'Deadline'],
[1, "Task A", None, None, None, None],
[2, "Task A", None, None, None, None],
[3, None, "Task A", None, "Task C", None],
[4, None, "Task A", None, "Task C", None],
[5, None, "Task A", None, "Task C", None],
[6, "Task C", "Task A", None, None, None],
[7, "Task C", None, None, None, None],
[8, None, None, "Task C", None, None],
[9, None, None, "Task C", None, None],
[10, None, None, "Task C", None, None],
[11, None, "Task C", "Task A", None, 'Task C'],
[12, None, None, "Task A", None, 'Task A'],
[13, None, None, "Task A", None, 'Task B'],
[14, None, None, None, "Task A", None],
[15, None, None, None, None, None],
[16, None, None, None, None, 'Task D'],
[17, None, None, None, None, None]
]
You need to sign in to view this answers
Leave feedback about this