Труды КНЦ вып. 11 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ) вып. 8/2020 (11)

Таблица 13. Реализация ограничения bin_packing в популярных библиотеках Constraint Programming Библиотека Choco GeCode JaCoP MiniZinc Имя ограничения binPacking binpacking Binpacking bin packing bin_packing_capa(C, V, W) - ограничение задает условие, каждый предмет i с весом W[i] должен быть помещен в корзину V[i], при этом вес каждой корзины не должен превышать C j] [10]. Пример 14: Пусть Vi £ {1, 2}, V 2 £ {1, 2}, V 3 £ {1, 2}, W = {4, 3, 1}, C = {4, 5} тогда всеми решениями, удовлетворяющими ограничению bin_packing_capa(C, {V1, V2, V3, V4}, W) будут: 1. V 1 = 1, V 2 = 2, V 3 = 2. 2. V 1 = 2, V 2 = 1, V 3 = 1. 3. V 1 = 2, V 2 = 1, V 3 = 2. Это ограничение имеет реализацию в популярных системах(библиотеках) программирования в ограничениях (таблица 14). Таблица 14. Реализация ограничения bin_packing_capa в популярных библиотеках Constraint Programming Библиотека Choco GeCode JaCoP MiniZinc Имя ограничения binPacking binpacking Binpacking bin_packing_capa cumulative(S, D, R, b) - ограничение задает условие, что в никакой момент времени, выполнение задач с временем начала S[i], продолжительностью D[i], потреблением ресурсов R [ i ] не превысит заданного порога b в потреблении ресурсов [ 1 0 ]. Пример £ ьтуст П 1 : {1, ... , 5}, S 2 £ {2, . 3 S 3}, 3, £ , 6}, 4 £ { . , 8}, D 1£ {4} , D 2 }, 6 £ D 3 £ {3, ..., 6}, £ С R },32, 2, £ , 6}, R 2£ {3} , R 3£ {1, 2}, , R4 3, £ 4}, b = 5, тогда всеми решениями, удовлетворяющими ограничению cumulative({S 1 , S 2, S 3, D,1 {}, to 3D ,2D , D 4} , {R 1 , R 2 , R 3 , R 4 }, b ) буду т: 1. S 1 ==1, S 2 = 3, S 3 = 5, S 4 = 1, D 1 = 4, D 2 = 6, D 3 = 3, D 4 M2, R 1 M 2, R 2 M3, R 3= 1, , R4 = 3. 2. S 1 ==1, S 2 = 3, S 3 = 5, S 4 = 1, D 1 = 4, D 2 II 6, 3D M 3, D 4 M2, R 1= 2 , R 2 M3, R 3= 2, , R4 = 3. 3. S 1 ==1, S 2 = 3, S 3 = 5, S 4 = 1, D 1 = 4, D 2 M6, D 3 M4, D 4 M2, R 1 M 2, R 2 M3, R 3= 1, , R4 = 3. 4. S 1 ==1, S 2 = 3, S 3 = 5, S 4 = 1, D 1 = 4, D 2 II 6, 3D M 4, D 4 M2, R 1 M 2, R 2 M3, R 3= 2, , R4 = 3. 5. S 1 ==1, S 2 = 3, S 3 = 6, S 4 = 1, D 1 = 4, D 2 II 6, 3D M 3, D 4 M2, R 1 M 2, R 2 M3, R 3= 1, , R4 = 3. 6. S 1 ==1, S 2 = 3, S 3 = 6, S 4 = 1, D 1 = 4, D 2 II 6, 3D M 3, D 4 M2, R 1 M 2, R 2 M3, R 3 = 2, R 4 = 3. 79