Как реализовать обратное программирование с назначением задач на основе списка приоритетов элементов в таблице Python? ⇐ Python

[Anonymous]

Мне нужно исправить программу с логикой обратного планирования, которая позволяет назначать задачи в порядке приоритета, в котором они появляются в заголовках столбцов Schedule_table.
Поскольку это обратный подход к планированию, размещение задач должно начинаться со строки столбца «Срок», где находится задача, которую нужно запланировать. Например, если мы начинаем с «Задачи C», задачи следует размещать, начиная с 13-го ряда вверх.
Если разместить задачи невозможно из-за недостаточного количества строк вверх, задачи должны начинаться с нескольких строк ниже «Крайнего срока», чтобы они помещались в соответствующие столбцы.
Таблица дорожной карты содержит информацию о том, какой столбец в Schedule_table (в данном случае «Машина 1», «Машина 2», «Машина 3» или «Машина 4») должна быть помещена каждая задача. Здесь также указывается количество последовательных часов (строк), которые следует оставить свободными для размещения указанные задачи. Помните, что свободная ячейка — это ячейка, которая по-прежнему содержит значение None.
Учитывая порядок, в котором столбцы отображаются в заголовках дорожной карты, сначала необходимо убедитесь, что все экземпляры «Задачи C» размещены, затем разместите все экземпляры «Задачи A», затем все экземпляры «Задачи B» и, наконец, убедитесь, что размещены все экземпляры «Задачи D».
< pre class="lang-py Prettyprint-override">

Код: Выделить всё

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

Вот входные данные:

Код: Выделить всё

# 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)

правильный вывод для этого случая должен быть следующим:

Код: Выделить всё

['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]

Обратите внимание, что в некоторых случаях, например «Задача А», задания могут не подходить, и нам нужно начать с двух строк раньше, чем строка «Срок сроков» в «Задаче А».< /p>

Код: Выделить всё

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]
]

И после запуска на две строки раньше он может разместить все экземпляры «Задачи А»:

Код: Выделить всё

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]
]

Подробнее здесь: https://stackoverflow.com/questions/791 ... s-priority