WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«2010 г. Ю. Н. СОТСКОВ, д-р физ.-мат. наук, Н. Г. ЕГОРОВА (Объединенный институт проблем информатики Национальной академии наук Беларуси, Минск, Беларусь), Ф. ВЕРНЕР, д-р ...»

Автоматика и телемеханика, № 10, 2010

c

2010 г. Ю. Н. СОТСКОВ, д-р физ.-мат. наук,

Н. Г. ЕГОРОВА

(Объединенный институт проблем информатики

Национальной академии наук Беларуси, Минск, Беларусь),

Ф. ВЕРНЕР, д-р философии

(Факультет математики Университета Отто фон Герике, Магдебург, Германия)

МИНИМИЗАЦИЯ СУММАРНОГО ВЗВЕШЕННОГО ВРЕМЕНИ

ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С НЕОПРЕДЕЛЕННЫМИ ДАННЫМИ:

МЕТОД, ОСНОВАННЫЙ НА УСТОЙЧИВОСТИ1

Исследуется задача построения расписания для одного прибора при неопределенных исходных данных: длительность обслуживания требования может оказаться равной любому действительному числу из заданного отрезка. Критерий оптимальности – минимизация суммарного взвешенного времени обслуживания требований. В качестве решения задачи с неопределенными данными рассматривается минимальное доминирующее множество перестановок требований, содержащее хотя бы одну оптимальную перестановку для каждой возможной реализации длительностей обслуживания требований. Для реализации оптимальной или близкой к оптимальной перестановки требований строится перестановка с наибольшим объемом многогранника устойчивости, который является подмножеством области устойчивости. Для поиска перестановки с наибольшим многогранником устойчивости разработан метод ветвей и границ .

Если несколько перестановок имеют наибольший объем многогранника устойчивости, то среди них выбирается перестановка, удовлетворяющая одному из двух простых эвристических правил. Качество построенных перестановок (насколько они близки к фактически оптимальным перестановкам) и эффективность разработанных программ (среднее время работы процессора при решении одного примера) продемонстрированы на множестве случайно сгенерированных примеров с количеством требований, заключенным в пределах 5 100 .



1. Введение Практические задачи построения оптимальных расписаний могут включать различные неопределенные параметры, и в литературе по исследованию операций представлено несколько подходов к решению таких задач. В широко распространенном стохастическом подходе [1] неопределенная длительность представляется случайной величиной с заранее известным законом распределения вероятностей. Если же нет достоверной информации для определения закона распределения вероятностей каждой случайной длительности, то необходимо использовать другие подходы [2, 3] .

В частности, в робастном подходе [4–6] лицо, принимающее решение, отдает предпочтение расписанию, при котором исключаются потери при наихудшем сценарии среди всех возможных реализаций длительностей обслуживания требований. Подход, основанный на устойчивости, разработанный в [7–12], объединяет анализ устойчивости, двустадийное принятие решений и минимальное доминирующее множество расписаний, которое определяет оптимальное покрытие всех возможных сценариев в том смысле, что оно содержит хотя бы одну оптимальную перестановку для каждой 1 Исследования первого автора проводились при поддержке Белорусского республиканского фонда фундаментальных исследований .

возможной реализации длительностей обслуживания требований [9–11]. Минимальное доминирующее множество расписаний (которое может быть построено на стадии оф-лайн) позволяет принимать он-лайн решения всякий раз, когда становится доступной информация о реализации обслуживания некоторых требований [9, 10] .



В этой статье рассматривается задача построения расписания для одного прибора с интервальными длительностями обслуживания требований. Для решения этой задачи точно (или приближенно) используется понятие многогранника устойчивости аналогичного шару устойчивости [9, 12–14], который применен в постоптимальном анализе. С помощью точной формулы для определения за время ( log ) многогранника устойчивости конкретной перестановки разработан метод ветвей и границ для определения перестановки с наибольшим объемом многогранника устойчивости. Представлены результаты экспериментов по нахождению перестановок с наибольшим объемом многогранника устойчивости, удовлетворяющих одному из двух эвристических правил .

–  –  –

Условие (3) выполняется для следующих пар упорядоченных требований:

{1, 3 }, {1, 4 }, {2, 3 }, {2, 4 }, {4, 5 }, {4, 6 }. В силу теоремы 2 выполняются бинарные отношения 1 3, 1 4, 2 3, 2 4, 4 5, 4 6 .

Минимальное доминирующее множество ( ) определяется орграфом = (, ) (редукция этого орграфа представлена на рис. 1). В силу теоремы 5 минимальное доминирующее множество определено однозначно для этого примера .

–  –  –

15, 5 10, 4 2, 1 4, 2 14, 5 19, 6 9, 4 13, 5 *, 0 12, 5 18, 6 6, 3 8, 4 1, 1 3, 2 5, 3 7, 4 11, 5 17, 6

–  –  –

(12) {1,..., } = {1,..., }, (,, ) (,, ) .

(13) Тогда вершина, может быть удалена из множества вершин, подлежащих дальнейшему ветвлению в дереве решений = (, ) .

Доказательство. Для каждой частичной перестановки, = (1,..., ), где 1, можно вычислить область устойчивости (,, ), используя равенство (11), и вычислить значение (,, ) как произведение относительных максимально возможных вариаций отношений весов к длительностям для всех требований, {1,..., } .

При назначении требования на позицию в перестановке, множество требований разбивается деревом на два подмножества относительно полной перестановки = (1, 2,..., 1,, +1..., ). Одно из подмножеств – множество требований {1,..., 1 }, расположенных перед требованием, второе из подмножеств – множество требований {+1..., }, расположенных после требования в перестановке. Максимально возможная вариация отношений веса к длительности для требования может быть вычислена по формулам (9) и (10). Очевидно, что результат вычислений не зависит от порядка следования требований внутри множества {1,..., 1 } и внутри множества {+1..., } .

Таким образом, если равенство (12) и неравенство (13) выполняются для перестановок, и,, то перестановка, может быть исключена из дальнейшего ветвления .

Возвращаясь к примеру, строим дерево решений, изображенное на рис. 2, где 5,3 = (1, 2, 3 ), 6,3 = (1, 2, 4 ), 7,4 = (1, 2, 3, 4 ), 8,4 = (1, 2, 4, 3 ), 9,4 = (1, 2, 4, 5 ), 10,4 = (1, 2, 4, 6 ), 11,5 = (1, 2, 3, 4, 5 ), 12,5 = (1, 2, 3, 4, 6 ), 13,5 = (1, 2, 4, 5, 3 ), 14,5 = (1, 2, 4, 5, 6 ), 15,5 = (1, 2, 4, 6, 3 ), 16,5 = (1, 2, 4, 6, 5 ), 17,6 = (1, 2, 3, 4, 5, 6 ), 18,6 = (1, 2, 3, 4, 6, 5 ), 19,6 = (1, 2, 4, 5, 6, 3 ) .





Нетрудно убедиться в том, что для вершин 3,2 = (1, 2 ) и 4,2 = (2, 1 ) в дереве решений = (, ) выполняется условие (13):

( 3,2, ) ( 4,2, ) .

–  –  –

В столбцах 6 и 7 указано количество задач (из 10 задач в серии), для которых перестановка с наибольшим относительным объемом области устойчивости дает то же оптимальное решение, что и оптимальное решение, полученное согласно алгоритмам SL и UL соответственно .

Средние и максимальные относительные погрешности целевой функции, вычисленные для построенных согласно алгоритму MAXSTABOX перестановок, относительно оптимальных значений целевой функции для фактических длительностей обслуживания требований, приведены в столбцах 8 и 10 для алгоритма SL и в столбцах 9 и 11 для алгоритма SU. В столбце 12 указано среднее время решения одной задачи из серии для алгоритма SL и алгоритма SU (это время одинаково для обоих алгоритмов) .

Из экспериментов видно, что условие (4) теоремы 3 выполняется для задач с малой погрешностью %, {0,1; 0,5} длительностей обслуживания требований (см. столбец 3) и для серии 11. Для всех задач этих серий перестановка с наибольшим относительным объемом области устойчивости дает оптимальное решение (столбцы 6, 7). Если один алгоритм превосходит другой, то соответствующее число в табл. 2 выделено жирным шрифтом .

5. Заключение В условиях жесткой конкуренции на современном инновационном и динамичном рынке предприятие должно использовать по максимуму оптимальную стратегию при принятии плановых решений, несмотря на неопределенность исходных данных .

Расписание, минимизирующее потери в наихудшем случае (такое расписание строится в робастном методе [4, 5]), является оптимальным относительно наихудшего сценария. Однако на практике наихудший сценарий реализуется довольно редко .

Действительно, маловероятно, что для фактического расписания все длительности обслуживания требований примут наиболее неблагоприятные для этого сценария значения. Следовательно, расписание, минимизирующее потери в наихудшем случае, может оказаться не конкурентоспособным для фактически реализованного сценария, который может быть очень далеким от наихудшего сценария. Кроме того, задача поиска расписания, минимизирующего потери в наихудшем случае для критерия, представляет собой NP-трудную задачу даже при двух возможных сценариях. Заметим в этой связи, что в большинстве реальных задач необходимо планировать большое количество требований, причем количество возможных сценариев также может быть довольно большим .

Стохастически оптимальное расписание для критерия ( ) (см. [1]), выбираемое из множества списочных статичных расписаний (такое расписание минимизирует ожидаемую сумму взвешенных моментов завершения обслуживания требований при условии, что требования в расписании упорядочены к начальному моменту времени согласно выбранному списку приоритетов требований), может быть построено по правилу наименьшей взвешенной длительности обслуживания (WSEPT):

требования следует обслуживать в порядке невозрастания отношения, где ( ) ( ) обозначает ожидаемую случайную длительность обслуживания требования (см. [1], с. 232). Такое стохастически оптимальное расписание будет фактически эффективным, если распределение вероятностей каждой случайной длительности обслуживания требования достоверно известно до начала построения расписания и если будет реализовано достаточно большое количество похожих сценариев для достаточно близких расписанческих задач. Однако такое стохастически оптимальное расписание может оказаться неконкурентоспособным для фактически реализованного (возможно, единичного) сценария. Кроме того, у предприятия может не быть достаточного количества попыток для компенсации потерь от использования стохастически оптимального расписания, которое оказалось не оптимальным для фактически реализованного сценария. Использование стохастически оптимальных расписаний в течение достаточно длительных промежутков времени (и для большого количества похожих сценариев) для предприятия может оказаться практически невозможным в силу того, что другие предприятия (его конкуренты) могут быть более успешными, благодаря достижению лучших результатов на рынке из-за более эффективной стратегии планирования .

На основе результатов [28] здесь из множеств возможных сценариев выбрано подмножество сценариев (, ), для которых перестановка заведомо является оптимальной. В силу определенных ограничений на множество требований множество ( ) оказывается единственным минимальным доминирующим множеством для неопределенной задачи 1. Следовательно, доминирующее множество ( ), являющееся минимальным по включению (см. условие (b) определения 1), является минимальным и по мощности. Ограничение на множество, которое обеспечивает единственность минимального доминирующего множества ( ), приводит к отождествлению соответствующих требований без потерь во множестве потенциально оптимальных расписаний и с уменьшением размерности = исходной задачи 1. Минимальное доминирующее множество перестановок ( ) определено однозначно для задачи 1, если выбирается только одно требование среди подмножества требований с одинаковыми отношениями веcов к длительностям обслуживания. В случае существования нескольких требований с одним тем же точечным отношением веса к длительностям обслуживания можно сократить число требований, рассматриваемых в минимальном доминирующем множестве. Таким образом, условие единственности ( ) не только не обременительно, но даже полезно. Было введено понятие многогранника устойчивости перестановки, который похож на шар ее устойчивости [12–14, 20]. При решении неопределенных задач многогранник устойчивости играет аналогичную роль, что и шар устойчивости [13, 14, 19–21, 29–31] в постоптимизационном анализе, когда исходные данные заранее известны и оптимальное решение построено для детерминированной задачи, а требуется определить область (шар) устойчивости построенного решения относительно возможных изменений исходных данных в пределах максимального радиуса .

Здесь была использована полученная в [28] точная формула вычисления многогранника устойчивости (, ) для любой фиксированной перестановки, которую можно реализовать за ( log ) действий. Разработан метод ветвей и границ для поиска перестановки с наибольшим относительным объемом многогранника устойчивости и представлены результаты точного и эвристического решения случайно сгенерированных задач на ноутбуке. В дальнейшем целесообразно продолжить исследования по использованию многогранника устойчивости для других неопределенных задач теории расписаний .

СПИСОК ЛИТЕРАТУРЫ

1. Pinedo M. Scheduling: Theory, Algorithms, and Systems. 2nd ed. USA. New Jersey:

Prentice-Hall, 2002 .

2. Aytug H., Lawley M. A., McKay K. et al. Executing production schedules in the face of uncertainties: a review and some future directions // Eur. J. Oper. Res. 2005. V. 161 .

P. 86–110 .

3. Sabuncuoglu I., Goren S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research // Int. J. Comput .

Integrated Manufactur. 2009. V. 22. No 2. P. 138–157 .

4. Daniels R.L., Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production // Management Sci. 1995. V. 41. No 2. P. 363–376 .

5. Kouvelis P., Yu G. Robust discrete optimization and its applications. USA, Boston: Kluwer Academic Publishers, 1997 .

6. Yang J., Yu G. On the robust single machine scheduling problem // J. Combinat. Optim .

2002. V. 6. P. 17–33 .

7. Lai T.-C., Sotskov Y.N., Sotskova N. et al. Optimal makespan scheduling with given bounds of processing times // Math. Comput. Model. 1997. V. 26. P. 67–86 .

8. Lai T.-C., Sotskov Y.N. Sequencing with uncertain numerical data for makespan minimization // J. Oper. Res. Soc. 1999. V. 50. P. 230–243 .

9. Sotskov Y.N., Sotskova N.Y. Teoriya raspisanii: sistemi s neopredelennimi chislovimi parametrami (Scheduling theory: Systems with uncertain numerical parameters), Belarus, Minsk: National Academy of Sciences of Belarus. United Institute of Informatics Problems, 2004 (in Russian) .

10. Matsveichuk N.M., Sotskov Y.N., Egorova, N.G. et al. Schedule execution for two-machine ow-shop with interval processing times // Math. Comput. Model. 2009. V. 49. No 5–6 .

P. 991–1011 .

11. Sotskov Y.N., Egorova N.G., Lai T.-C. Minimizing total weighted ow time of a set of jobs with interval processing times // Math. Comput. Model. 2009. V. 50. P. 556–573 .

12. Lai T-C, Sotskov Y.N., Sotskova N.Y. et al. Mean ow time minimization with given bounds of processing times // Eur. J. Oper. Res. 2004. V. 159. No 3. P. 558–573 .

13. Sotskov Y.N., Wagelmans A.P.M., Werner F. On the calculation of the stability radius of an optimal or an approximate schedule // Ann. Oper. Res. 1998. V. 83. P. 213–252 .

14. Sotskov Y.N., Sotskova N.Y., Werner F. Stability of an optimal schedule in a job shop // Omega. 1997. V. 25. No 4. P. 397–414 .

15. Graham R.L., Lawler E.L., Lenstra J.K. et al. Optimization and approximation in deterministic sequencing and scheduling. A survey // Ann. Discr. Math. 1976. V. 5. P. 287–326 .

16. Smith W.E. Various optimizers for single-stage production // Nav. Res. Logist. Quarterly .

1956. V. 3. No 1. P. 59–66 .

17. Kasperski A., Zielinski P. A 2-approximation algorithm for interval data minmax regret sequencing problems with total ow time criterion // Oper. Res. Lett. 2008. V. 36. P. 343– 344 .

18. Montemanni R. A mixed integer programming formulation for the total ow time single machine robust scheduling problem with interval data // J. Math. Model. Algorith. 2007 .

V. 6. P. 287–296 .

19. Sotskov Y.N., Dolgui A., Portmann M.-C. Stability analysis of optimal balance for assembly line with xed cycle time // Eur. J. Oper. Res. 2006. V. 168. No 3. P. 783–797 .

20. Sotskov Y.N. Stability of an optimal schedule // Eur. J. Oper. Res. 1991. V. 55. P. 91–102 .

21. Sotskov Y.N., Tanaev V.S., Werner F. Stability radius of an optimal schedule: A survey and recent developments, Yu G. (Editor) // Industr. Appl. Combinat. Optim. USA. Boston, MA: Kluwer Academic Publishers, 1998. P. 72–108 .

22. Сотскова Н.Ю., Танаев В.С. О реализации оптимального расписания в условиях неопределенности длительностей операций // Докл. Нац. АН Беларуси. 1998. Т. 42 .

No 5. C. 8–12 .

23. Allahverdi A., Sotskov Y.N. Two-machine owshop minimum-length scheduling problem with random and bounded processing times // Int. Transactions Oper. Res. 2003. V. 10 .

P. 65–76 .

24. Allahverdi A., Aldowaisan T., Sotskov Y.N. Two-machine owshop scheduling problem to minimize makespan or total completion time with random and bounded setup times // Int .

J. Math. Math. Sci. 2003. V. 39. P. 2475–2486 .

25. Ng C.T., Matsveichuk N.M., Sotskov Y.N. et al. Two-machine ow-shop minimum-length scheduling with interval processing times // Asia-Pacic J. Oper. Res. 2009. V. 26. No 6 .

P. 1–20 .

26. Sotskov Y.N., Allahverdi A., Lai T.-C. Flowshop scheduling problem to minimize total completion time with random and bounded processing times // J. Oper. Res. Soc. 2004 .

V. 55. P. 277–286 .

27. Coman E.G. Computer and Job-Shop Scheduling Theory. USA: John Wiley & Sons, 1976 .

28. Sotskov Y.N., Lai T.-C. Minimizing total weighted completion time under uncertainty using stability box and dominance // Math. Comput. Model. (submitted) .

29. Emelichev V.A., Girlich E.N., Nikulin Y.V. et al. Stability and regularization radius of vector problems of integer linear programming // Optim. 2002. V. 51. No 4. P. 645–676 .

30. Emelichev V.A., Krichko V.N., Nikulin Y.V. The stability radius of an ecient solution in mimimax Boolean programming problem // Control Cybernet. 2004. V. 33. No 1. P. 127– 132 .

31. Emelichev V.A., Kuz’min K.G., Leonovich, A.M., Stability in the combinatorial vector optimization problems // Automat. Remote Control. 2004. V. 65. No 2. P. 227–240 .

Статья представлена к публикации членом редколлегии А.А. Лазаревым.




Похожие работы:

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ НАЦИОНАЛЬНЫЙ ГОСТР СТАНДАРТ МЭК 62279— РОССИЙСКОЙ ФЕДЕРАЦИИ Железные дороги СИСТЕМЫ СВЯЗИ, СИГНАЛИЗАЦИИ И ОБРАБОТКИ ДАННЫХ. ПРОГРАММНОЕ ОБЕ...»

«Технический Семинар по Саранчовым на Кавказе и в Центральной Азии (КЦА) Пушкин, Российская Федерация, 26-30 октября 2015 г. Пилотный проект по разработке системы мониторинга качеств...»

«Министерство образования и науки РФ ФГЬОУ ВО "Дагестанский государственный технический университет" Кафедра Социально-культурного сервиса и туризма Утверждаю Ректор Ф Г Ь О У ВО "ДГТУ", Г.А.Исмаилов ж гй. Щ 2016 г. JL 3. OJL. П РО Г РА М М А ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ по...»

«© Г.Г. Каркашадзе, А.М.-Б. Хаутиев, 2015 УДК 622.411.33:622.831 Г.Г. Каркашадзе, А.М.-Б. Хаутиев МЕХАНИЗМ ПОВЫШЕНИЯ ГАЗОПРОНИЦАЕМОСТИ УГОЛЬНОГО ПЛАСТА В ПРОЦЕССЕ ЦИКЛИЧЕСКОЙ СОРБЦИОННОЙ УСАДКИ И РАЗБУХАНИЯ УГЛЯ Представлено техническо...»

«УДК 821.161.1-94 ББК 84(2Рос=Рус)6-44 Б46 Бенуа, Софья. Мария Магдалина. Тайная супруга Иисуса Христа / Софья БеБ46 нуа. – Москва : Алгоритм, 2018. – 208 с. – (Главная кинопремьера года). ISBN 978-5-906995-99-5 Мария Магдалина – одна из самых таинственных личностей Евангелия. Представление о ней люди составили главным образом по картинам на биб...»

«САВИНЫХ Вадим Владимирович ПОВЫШЕНИЕ КАЧЕСТВА ЭЛЕКТРИЧЕСКОЙ ЭНЕРГИИ В РАСПРЕДЕЛИТЕЛЬНЫХ СЕТЯХ ДО 1000 В НА ОСНОВЕ МЕТОДА ПРЕОБРАЗОВАНИЯ КООРДИНАТ СИММЕТРИЧНЫХ И ОРТОГОНАЛЬНЫХ СОСТАВЛЯЮЩИХ Специальность 05.14.02 – Электрические станции и электроэнергетическ...»

«5 Раздел 1. ОБОСНОВАНИЕ ИНВЕСТИЦИЙ В СТРОИТЕЛЬСТВО, РЕКОНСТРУКЦИЮ И ТЕХНИЧЕСКОЕ ПЕРЕВООРУЖЕНИЕ а) Техническая и экономическая целесообразность. Исторически проектирование ТСС в России было направлено по пути упрощенных решений в виде тупиковых (древовидных) схем, как правило, с открытой схемой горячего...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.