Page 90 - 4495
P. 90

Обмеження  alldifferent  (List)  (чи  alldistinct)  [42,  43]  означає  що,
            множина змінних у списку List повинна мати попарно різні n величин.
                  Обмеження alldifferent можна також інтерпретувати як зада-
            чу планування доступу до певних ресурсів, наприклад унарних ресур-

            сів  (unary  resource).  Диз’юнктивні  обмеження  розширюють  можли-
            вість застосовування alldifferent для змінних різної області видимості.
            У загальному такі обмеження належать до класу диз’юнктивних про-

            блем планування [44, 45, 46, 47, 48, 49]. Обмеження задаються таким
            чином, щоб не задавати переривання окремих часткових задач. Задачі
            описуються початковим часом StartJ та тривалістю DurationJ
                             disjunctive([Start1,...,StartN], [Dura-

                                         tion1,...,DurationN]),
            де  кожен  StartJ  та  DurationJ  є  доменними  змінними  з  скінченними

            границями чи цілими числами.
                  Обмеження  кумулятивного  планування  (cumulative  scheduling)
            [50, 51, 46, 47, 48, 49] у проекті CHIP для розв’язання задач плану-
            вання та розміщення ресурсів [52]. Воно забезпечує можливість пара-

            лельного виконання певним ресурсом кілька задач одночасно, забез-
            печуючи тим самим підтримку ємності дискретних ресурсів. Якщо є
            N  задач,  кожна  з  яких  починається  в  точно  визначений  час  (StartI),

            має точну тривалість (DurationI), і використовує точну кількість ре-
            сурсів (ResourceI), тоді сума ресурсів, що використовується всіми за-
            дачами не повинна перевищувати ResourceLimit в будь-який момент

            часу. Синтаксис обмеження такий
                  cumulative([Start1,...,StartN],                                                 [Dura-
            tion1,...,DurationN],

                  [Resource1,...,ResourceN], ResourceLimit),
                  де  елементи  всіх  змінних  разом  з  ResourceLimit  є  доменними
            змінним з скінченними границями.
                  У роботі [52] представлено основні напрями використання куму-

            лятивного  обмеження.  Представлено  можливості  кумулятивних  об-
            межень,  зокрема  наведено  приклад  зведення  кумулятивного  обме-

            ження до диз’юнктивної проблеми планування. А також застосування
            кумулятивних  обмежень  у  випадку  проблеми  складання  розкладу.
            Семантичне представлення базується на обмеженнях класу atmost що
            реалізовується у вигляді задач одиничного розподілу ресурсів та оди-

            ничної тривалості.
                  cumulative(Starts,ListOf1,ListOf1,ResourceLimit) =
                  {at-




                                                           90
   85   86   87   88   89   90   91   92   93   94   95