?
On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty
Рассматривается классическая задача теории расписаний на одной машине с заданными моментами поступления требований. Целевой функцией является минимизация некоторой функции штрафа.Задача является NP-трудной в сильном смысле. Для этой задачи мы вводим двойственную и обратную задачу и показываем, что обе они могут быть решены за полиномиальное время. Поскольку двойственная задача дает нижнюю границу для оптимального значения целевой функции исходной задачи, мы используем оптимальное значение целевой функции подзадачи двойственной задачи в алгоритме ветвей и границ для поиска решения исходной задачи теории расписаний для одного прибора. Представлены некоторые начальные результаты вычислений для тестовых примеров с количеством требований до 20.
Язык:
английский