Ищу оптимальный алгоритм онлайн-назначения

Я ищу решение проблемы назначения, когда задачи приходят и их нужно назначать последовательно, но вы можете заставить задачи ждать до K периодов.

Формально пусть будет упорядоченная последовательность задач aabbaba ... и упорядоченная последовательность ресурсов ABBABAA ... , и система может использовать боковой стек. Цель состоит в том, чтобы сопоставить наибольшее количество a (соответственно b ) задач с A (соответственно B ) ресурсами. Ограничения следующие: каждый период i программа получает ресурс i и назначает его задаче. Ресурс назначается задаче из стека, или он продолжает считывать из последовательности задач по порядку. Каждая считываемая задача может быть сразу назначена ресурсу i или может быть помещена в стек, ЕСЛИ она будет ждать там менее K периодов и будет назначена этому совпадению ( а-> А, б-> В).

Если K = 0 , то i -я задача должна быть назначена i -ому ресурсу, что очень плохо. Если K> 0 , вы можете добиться большего с помощью жадного алгоритма. Какое оптимальное решение?

Уточнение:

Обозначьте назначение перестановкой m , где m (i) = j означает, что ресурс j назначен задаче ] i . Если нет стека m (i) = i . При наличии стека задачи могут быть назначены не по порядку, но если задача позже, чем i помещается в стек, то i должно быть назначено одно из следующих K ресурсов. То есть присвоение допустимо, если для всех задач i :

m (i) <= Min {m (i ') s.t. i '> i} + K

Я ищу алгоритм, который найдет задание с минимальным количеством пропущенных назначений (aB или bA) из всех назначений, удовлетворяющих ограничениям.