Теория на разписанията: Задачи от вида "Job Shop"

Теорията на разписанията е сравнително нов раздел от математиката (приложната математика), породен от различни практики в промишлеността и транспорта, в икономиката, в социалните науки и други, в които следва да се решават задачи, свързани с подреждане на някакво множество от дейности. Досегашното ѝ развитие е насочено главно към проблеми, при които средствата за изпълнение на различни видове операции и времето за тяхното изпълнение са определени и предварително известни. (Deterministic Mashine Scheduling). Подреждането на множество от някакъв вид (самолети, влакове, учебни занятия, машинни детайли, пакети от данни, групи и други) за изпълнение върху елементите му на множество от различни, последователно изпълнявани операции, услуги, от различен вид съображения, машини, компютри, прибори, групи от изпълнители и т.н., съобразно определени критерии са задачи, които възникват непрекъснато. За тяхното своевременно решаване е необходимо изграждането на пакети от ефективни методи. Първият вид множества ще бъдат наричани поръчки (jobs), а средствата, с които се изпълняват операциите, услугите, дейностите - машини (machines).

Университетско издателство Св. Климент Охридски
София, 1164
жк. Лозенец, ул. Златовръх 30
unipress@unipress.bg

Въведение
Основни понятия от комбинаториката и от теорията на графите

• Комбинаторика
• Съединения с наредба
• Съединения без наредба
• Теорема за включванията и изключванията
• Някои типични задачи
• Теория на графите. Основни понятия
• Неориентирани графи
• Видове неориентирани графи, операции и последователности от ребра и върхове
• Свързаност на неориентиран граф
• Ориентиран граф. Последователности от дъги и върхове. Свързаност
• Ориентирано дърво. Матрици на инцидентностите и на съседствата. Метрика. Факторизации
• Приложения

Теория на NP-пълните (трудните) задачи. Полиномиална сводимост

• Задачи за разпознаване. Кодиране
• Машина на Тюринг. Клас P и клас NP
• Детерминирана машина на Тюринг
• Недетерминирана машина на Тюринг
• Полиномиална и псевдополиномиална сводимост. NP-трудни задачи

Класификация. Задачи от вида Job Shop

• Понятия. Основни ограничения
• Класификация на задачите от TP
• Машинно обкръжение
• Характеристики на поръчките
• Критерии за оптималност
• Класификация и сводимост
• Някои задачи от вида Job Shop. Еталонни задачи

Обслужване на n поръчки от две машини и обслужване на две поръчки от m машини

• Обслужване на n поръчки от две машини
• Обслужване на n поръчки от две машинни без прекъсване на операциите и без повторно използване на машините
• Обслужване на n поръчки от две машини с повторно използване на машините
• Обслужване на две поръчки от m машини
• Обслужване на две поръчки без повторно използване на машините
• Обслужване на две поръчки от m машини с неколкократно обработване на машините
• Трудност на задачите

Множество поръчки, обработвани от m ≥ 3 машини

• Понятия, твърдения, ограничения
• m ≥ 3. Всички поръчки (n ≥ 4) имат първа операция на първа машина
• m = 3, n ≥ 4
• m = 4, n ≥ 4
• m ≥ 4, n ≥ 4
• m ≥ 3. Всички поръчки (n ≥ 4) имат междинна операция на междинна машина
• m = 3, n ≥ 4
• m = 4, n ≥ 4
• m ≥ 4, n ≥ 4
• m ≥ 3. Всички поръчки (n ≥ 4) имат последна операция на последна машина
• m = 3, n ≥ 4
• m = 4, n ≥ 4
• m ≥ 4, n ≥ 4

Множество поръчки, обработвани от m ≥ 3 машини (продължение)

• Общ случай с валидно неравенство
• Изпълнено неравенство
• Общ случай с валидно неравенство
• Първа операция се изпълнява от машина I
• Определена междинна операция на всички поръчки се изпълнява от една междинна машина
• Последната операция на всички поръчки се изпълнява от последната машина

Литература