Google OR-Tools:解决方案无法使用python收敛与任务大小的分配 [英] Google OR-Tools : Solution unable to converge for Assignment with Task Sizes using python
本文介绍了Google OR-Tools:解决方案无法使用python收敛与任务大小的分配的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我试图通过添加多维大小"(需求)和"total_size_max"来详细说明任务大小分配"示例.
I tried to elaborate on the Assignment with Task Sizes example by adding a multi-dimensional "size"(demand) and "total_size_max" .
该解决方案似乎决定将所有内容分配给1个工作人员，尽管事实上还有其他人可用.运行时的结果将所有内容分配给worker(机器18).
The solution seems to decide to allocate everything to 1 worker only despite the fact that others are available. The result when run allocates everything to worker(machine 18).
样本输出:
Machine 18 is assigned to produce Component 0 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 1 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 2 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 3 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 4 with minimum Cycle_Time = 10000000
Machine 18 is assigned to produce Component 5 with minimum Cycle_Time = 10000000
代码:
# -*- coding: utf-8 -*-
from __future__ import print_function
from ortools.sat.python import cp_model
import time
import numpy as np
def main():
model = cp_model.CpModel()
start = time.time()
# cost = machines on rows and components on columns with least cycle_time
cost = [[7.995722268,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.995722268,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.995722268,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.995722268,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.764712938,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.64179678,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.764712938,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,26.10110138,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,26.10110138,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,24.79202174,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,27.72432227,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,29.63946277,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,29.4907994,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,24.79202174,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,27.72432227,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,29.63946277,10000000,10000000,10000000],
[10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.271052178,10000000,10000000,10000000,10000000,10000000,10000000],
[8.213437897,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.213437897,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.213437897,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.213437897,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.372568825,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.282863934,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,15.49746661,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,14.36944353,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,14.95278777,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,13.33333333,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,13.33333333,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,6.194286893,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,14.56521739,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,17.57157641,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.194286893,10000000,14.56521739,10000000,10000000,10000000,10000000],
[8.076237035,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.076237035,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.076237035,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.076237035,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.400797794,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[8.019304639,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.019304639,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.019304639,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.019304639,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.496583613,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,3.778990587,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,11.51228733,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,11.06301248,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,4.492667454,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,5.512785364,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358,10000000,10000000,10000000,10000000,10000000,10000000,10000000,1.780837358,10000000,1.780837358],
[10000000,10000000,10000000,10000000,10000000,7.755011055,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.755011055,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.755011055,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,7.755011055,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,25.45422456,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,29.69460764,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,32.00169225,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,25.45422456,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,29.69460764,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,10000000,10000000,10000000,10000000,10000000,28.19319991,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,27.13193117,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,26.59704717,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,28.19319991,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,27.13193117,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,21.5723175,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,8.455696203,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000],
[10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000,6.776314217,10000000,10000000,10000000,10000000,10000000,10000000,10000000,10000000]
]
#costList = [round(x) for x in cost]
costlist = np.round(cost).astype(int).tolist()
# demand for each component
demand = [28,28,28,28,28,28,28,28,28,56,28,30,30,30,30,30,30,30,30,30,60,176,176,176,176,176,176,176,176,176,352,194,194,194,194,194,194,194,194,194,388,56,56,56,56,56,56,56,56,56,112,56,149,149,149,149,149,149,149,149,149,298,911,911,911,911,911,911,911,911,911,1822]
# convert to numpy array for division
arr = np.array(cost)
# total available hours
available_hrs = 2592000
total_size_max = available_hrs / arr
total_size_max = total_size_max.astype(int)
num_workers = len(cost)
num_tasks = len(cost[1])
# Variables
x = []
for i in range(num_workers):
t = []
for j in range(num_tasks):
t.append(model.NewIntVar(0, 1, "x[%i,%i]" % (i, j)))
x.append(t)
x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)]
# Constraints
# Each component is assigned to at least one machine.
[model.Add(sum(x[i][j] for i in range(num_workers)) >= 1)
for j in range(num_tasks)]
# Total demand of component for each machine is at most total_size_max(available_hrs/cycle_time).
[model.Add(sum(demand[j] * x[i][j] for j in range(num_tasks)) <= total_size_max[i][j])
for i in range(num_workers)]
model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, costlist)]))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
print('Minimum cost = %i' % solver.ObjectiveValue())
print()
for i in range(num_workers):
for j in range(num_tasks):
if solver.Value(x[i][j]) == 1:
print('Machine ', i, ' is assigned to produce Component ', j, ' with minimum Cycle_Time = ', cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
if __name__ == '__main__':
main()
我从示例示例中获取了此信息，并根据需要调整了输入数据.有人可以帮助解决此问题吗?
I took this from the sample example and tweaked input data according to my need. Can someone help resolve this issue?
预期结果是应根据需求分配时间最短的机器
Expected result is that the machine with lowest time should be assigned according to the demand
推荐答案
以下是完整答案:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 14 00:52:54 2019
@author: 320048504
"""
from __future__ import print_function
from ortools.sat.python import cp_model
import time
import numpy as np
def main():
model = cp_model.CpModel()
start = time.time()
cost = [[
7.995722268, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7.995722268, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7.995722268, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 7.995722268, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, 6.764712938, -1, -1, -1, -1, -1, -1, -1,
-1, -1, 6.64179678, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 6.764712938, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, 26.10110138, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, 26.10110138, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, 24.79202174, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 27.72432227, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 29.63946277, -1, -1, -1, -1, -1, -1, -1, -1, -1,
29.4907994, -1, -1, -1, -1, -1, -1, -1, -1, -1, 24.79202174,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 27.72432227, -1, -1,
-1, -1, -1, -1, -1, -1, -1, 29.63946277, -1, -1, -1
],
[
-1, -1, -1, 6.271052178, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 6.271052178, -1, -1, -1, -1, -1, -1, -1, -1, -1,
6.271052178, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6.271052178,
-1, -1, -1, -1, -1, -1, -1, -1, -1, 6.271052178, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, 6.271052178, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 6.271052178, -1, -1, -1, -1, -1, -1
],
[
8.213437897, -1, 4.372568825, -1, -1, -1, -1, -1, -1, -1, -1,
8.213437897, -1, 4.372568825, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 4.372568825, -1, -1, -1, -1, -1, -1, -1, -1, -1,
4.372568825, -1, -1, -1, -1, -1, -1, -1, 8.213437897, -1,
4.372568825, -1, -1, -1, -1, -1, -1, -1, -1, 8.213437897, -1,
4.372568825, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4.372568825,
-1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, 6.282863934, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 6.282863934, -1, -1, -1, -1, -1, -1, -1, -1, -1,
6.282863934, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6.282863934,
-1, -1, -1, -1, -1, -1, -1, -1, -1, 6.282863934, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, 6.282863934, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 6.282863934, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 15.49746661, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 14.36944353, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 14.95278777, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 13.33333333, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 13.33333333, -1, -1, -1, -1
],
[
-1, -1, -1, 6.194286893, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 6.194286893, -1, -1, -1, -1, -1, -1, -1, -1, -1,
6.194286893, -1, 14.56521739, -1, -1, -1, -1, -1, -1, -1,
6.194286893, -1, 17.57157641, -1, -1, -1, -1, -1, -1, -1,
6.194286893, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
6.194286893, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6.194286893,
-1, 14.56521739, -1, -1, -1, -1
],
[
8.076237035, -1, 4.400797794, -1, -1, -1, -1, -1, -1, -1, -1,
8.076237035, -1, 4.400797794, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 4.400797794, -1, -1, -1, -1, -1, -1, -1, -1, -1,
4.400797794, -1, -1, -1, -1, -1, -1, -1, 8.076237035, -1,
4.400797794, -1, -1, -1, -1, -1, -1, -1, -1, 8.076237035, -1,
4.400797794, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4.400797794,
-1, -1, -1, -1, -1, -1, -1
],
[
8.019304639, -1, 4.496583613, -1, -1, -1, -1, -1, -1, -1, -1,
8.019304639, -1, 4.496583613, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 4.496583613, -1, -1, -1, -1, -1, -1, -1, -1, -1,
4.496583613, -1, -1, -1, -1, -1, -1, -1, 8.019304639, -1,
4.496583613, -1, -1, -1, -1, -1, -1, -1, -1, 8.019304639, -1,
4.496583613, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4.496583613,
-1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, 3.778990587, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, 3.778990587, -1, -1, -1, -1, -1, -1, -1, -1, -1,
3.778990587, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3.778990587,
-1, -1, -1, -1, -1, -1, -1, -1, -1, 3.778990587, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, 3.778990587, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 3.778990587, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
11.51228733, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, 4.492667454, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
4.492667454, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4.492667454,
-1, -1, -1, -1, -1, -1, -1, 11.06301248, -1, 4.492667454, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 4.492667454, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 4.492667454, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 4.492667454, -1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, -1, -1, 5.512785364, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 5.512785364, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 5.512785364, -1, -1, -1, -1, -1, -1, -1, -1, -1,
5.512785364, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5.512785364,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5.512785364, -1, -1,
-1, -1, -1, -1, -1, -1, -1, 5.512785364, -1
],
[
-1, -1, -1, -1, -1, -1, -1, 1.780837358, -1, 1.780837358,
1.780837358, -1, -1, -1, -1, -1, -1, -1, 1.780837358, -1,
1.780837358, -1, -1, -1, -1, -1, -1, -1, 1.780837358, -1,
1.780837358, -1, -1, -1, -1, -1, -1, -1, 1.780837358, -1,
1.780837358, -1, -1, -1, -1, -1, -1, -1, 1.780837358, -1,
1.780837358, 1.780837358, -1, -1, -1, -1, -1, -1, -1,
1.780837358, -1, 1.780837358, -1, -1, -1, -1, -1, -1, -1,
1.780837358, -1, 1.780837358
],
[
-1, -1, -1, -1, -1, 7.755011055, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, 7.755011055, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 7.755011055, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, 7.755011055, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, 25.45422456, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 29.69460764, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 32.00169225, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 25.45422456, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 29.69460764, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1
],
[
-1, -1, -1, -1, -1, -1, 28.19319991, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 27.13193117, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26.59704717, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 28.19319991, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 27.13193117, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1
],
[
-1, 21.5723175, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
21.5723175, -1, -1, -1, -1, -1, -1, -1, -1, -1, 21.5723175, -1,
-1, -1, -1, -1, -1, -1, -1, -1, 21.5723175, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 21.5723175, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 21.5723175, -1, -1, -1, -1, -1, -1, -1, -1, -1, 21.5723175,
-1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, 8.455696203, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
8.455696203, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8.455696203,
-1, -1, -1, -1, -1, -1, -1, -1, -1, 8.455696203, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 8.455696203, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 8.455696203, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 8.455696203, -1, -1, -1, -1, -1, -1, -1, -1
],
[
-1, 6.776314217, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
6.776314217, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6.776314217,
-1, -1, -1, -1, -1, -1, -1, -1, -1, 6.776314217, -1, -1, -1,
-1, -1, -1, -1, -1, -1, 6.776314217, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, 6.776314217, -1, -1, -1, -1, -1, -1, -1, -1,
-1, 6.776314217, -1, -1, -1, -1, -1, -1, -1, -1
]]
scaling = 100
int_cost = [[int(round(x * scaling)) for x in line] for line in cost]
# demand for each component
demand = [
28, 28, 28, 28, 28, 28, 28, 28, 28, 56, 28, 30, 30, 30, 30, 30, 30, 30,
30, 30, 60, 176, 176, 176, 176, 176, 176, 176, 176, 176, 352, 194, 194,
194, 194, 194, 194, 194, 194, 194, 388, 56, 56, 56, 56, 56, 56, 56, 56,
56, 112, 56, 149, 149, 149, 149, 149, 149, 149, 149, 149, 298, 911,
911, 911, 911, 911, 911, 911, 911, 911, 1822
]
# total available hours
available_hrs = 2592000
num_workers = len(int_cost)
num_tasks = len(int_cost[1])
print('num_workers =', num_workers, ', num_tasks =', num_tasks)
# Variables
x = [[
0 if int_cost[i][j] < 0 else model.NewBoolVar('x[%i,%i]' % (i, j))
for j in range(num_tasks)
] for i in range(num_workers)]
# Constraints
# For each component, demand is met.
for j in range(num_tasks):
model.Add(
sum(x[i][j] for i in range(num_workers)
if int_cost[i][j] >= 0) == 1)
# Total worked hours for each machine is at most available_hrs.
for i in range(num_workers):
model.Add(
sum(x[i][j] * int_cost[i][j] * demand[j] for j in range(num_tasks)
if int_cost[i][j] >= 0) <= available_hrs * scaling)
# Objective: minimize worked hours.
model.Minimize(
sum(x[i][j] * int_cost[i][j] * demand[j] for i in range(num_workers)
for j in range(num_tasks) if int_cost[i][j] >= 0))
model.Proto().objective.scaling_factor = 1.0 / scaling
# Solve.
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_search_workers = 8
status = solver.Solve(model)
# Print solution.
if status == cp_model.OPTIMAL:
print('Minimum cost = %f' % solver.ObjectiveValue())
print()
for i in range(num_workers):
for j in range(num_tasks):
qty = 0 if cost[i][j] == -1 else solver.Value(x[i][j])
if qty > 0:
print('Machine ', i, ' is assigned to produce Component ',
j, ' with minimum Cycle_Time = ', cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
if __name__ == '__main__':
main()
我增加了成本调整以提高精度
I have added cost scaling to improve precision
以下是输出:
Minimum cost = 123887.560000
Machine 0 is assigned to produce Component 0 with minimum Cycle_Time = 7.995722268
Machine 0 is assigned to produce Component 11 with minimum Cycle_Time = 7.995722268
...
Machine 24 is assigned to produce Component 53 with minimum Cycle_Time = 6.776314217
Machine 24 is assigned to produce Component 63 with minimum Cycle_Time = 6.776314217
Time = 0.0834 seconds
这篇关于Google OR-Tools:解决方案无法使用python收敛与任务大小的分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
