Мера неопределенности задачи Беллмана–Джонсона с интервальными длительностями

Abstract

Розглянуто задачу оптимального за швидкодією обслуговування двома послідовними пристроями n вимог з однаковими технологічними маршрутами. Тривалість операції з обслуговування вимоги стає відомою лише на момент завершення її обслуговування пристроєм (при складанні розкладу відомо, що тривалість операції повинна належати заданому відрізку). Для такої задачі вводиться міра невизначеності, основана на потужності мінімальної домінуючої множини переставлень n вимог. Отримано критерій єдиності мінімальної домінуючої множини.

Time-optimal processing of n jobs with identical processing routes by two different machines is considered. The duration of processing becomes known only upon job completion (it is only known to belong to a given interval). For such a problem, an uncertainty measure is introduced. This measure is based on the cardinality of the minimal dominant set of permutations of n jobs. The uniqueness criterion for the minimal dominant set is obtained.