Більш швидкий спосіб приблизного планування однаково розділених завдань з перемиканнями на єдиній машині зі зростанням значущості наступних завдань
Анотація
Мінімізація загального зваженого часу завершення є дуже важливою ціллю в організації та виконанні багатоетапних процесів обчислень, диспетчеризації, виробництва, компонування, будівництва тощо. Ця задача розв’язується теорією розкладів. Теорія розкладів надає підходи для знаходження як точних, так і приблизних розкладів виконання завдань. Точний розклад дозволяє виконати завдання за мінімальний загальний зважений час завершення. Приблизний розклад дозволяє виконати завдання за час, котрий є достатньо близьким до мінімального загального зваженого часу завершення. Однак приблизний розклад отримують незрівнянно швидше, тоді як точні підходи стають практично нездійсненними уже для декількох десятків завдань. Тому розглядається одна ефективна евристика для знаходження приблизного розкладу для випадку однаково розділених завдань з перемиканнями на єдиній машині зі зростанням значущості наступних завдань. При цьому вивчається питання того, чи призводить певний порядок уведення дат запуску завдань до різного часу обчислень. Встановлюється, що спадний порядок завдань має відносну перевагу в 1 % при плануванні більш ніж 200 завдань. Зі зростанням кількості завдань від 1000 ця перевага має незначну тенденцію до зростання. Така перевага може досягти 22 %. Зокрема, послідовність з 240 задач зі 75000 завдань у кожній, де кожне завдання складається з 5 частин, за спадного порядку завдань розплановується за 17.2973 години, тоді як ця ж послідовність за зростаючого порядку завдань розплановується за 21.0691 години. Максимально можливий виграш часу обчислень досягається при роботі з більш довгими послідовностями задач планування завдань більшого розміру.
Завантаження
Посилання
/Посилання
M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer Int. Publ., 2016.
P. Brucker, Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2007.
H. Belouadah et al., “Scheduling with release dates on a single machine to minimize total weighted completion time”, Discrete Applied Mathematics, vol. 36, iss. 3, pp. 213 — 231, 1992.
M. L. Pinedo, Planning and Scheduling in Manufacturing and Services. Springer, 2009.
I. A. Mandzyuk and V. V. Romanuke, “Rheometric research of polypropylene Licocene PP2602 melts”, Archives of Materials Science and Engineering, vol. 50, iss. 1, pp. 31 — 35, 2011.
V. V. Romanuke, “Appropriate number and allocation of ReLUs in convolutional neural networks”, Research Bulletin of NTUU “Kyiv Polytechnic Institute”, no. 1, pp. 69 — 78, 2017.
V. V. Romanuke, “Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality”, KPI Science News, no. 4, pp. 38 — 53, 2018.
Pinedo M. L. Scheduling: Theory, Algorithms, and Systems. — Springer Int. Publ., 2016. — 670 p.
Brucker P. Scheduling Algorithms. — Springer-Verlag Berlin Heidelberg, 2007. — 371 p.
Belouadah H., Posner M. E., Potts C. N. Scheduling with release dates on a single machine to minimize total weighted completion time // Discrete Applied Mathematics. — 1992. — Vol. 36, Iss. 3. — P. 213 — 231.
Pinedo M. L. Planning and Scheduling in Manufacturing and Services. — Springer, 2009. — 536 p.
Mandzyuk I. A., Romanuke V. V. Rheometric research of polypropylene Licocene PP2602 melts // Archives of Materials Science and Engineering. — 2011. — Vol. 50, Iss. 1. — P. 31 — 35.
Romanuke V. V. Appropriate number and allocation of ReLUs in convolutional neural networks // Research Bulletin of NTUU “Kyiv Polytechnic Institute”. — 2017. — No. 1. — P. 69 — 78.
Romanuke V. V. Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality // KPI Science News. — 2018. — No. 4. — P. 38 — 53.
