n个工人作业分配问题分支限界法python实现

#-*- coding:utf-8 -*- import numpy as np import os #打印二维数组的函数，用以显示计算过程 def printTable(Data): for i in range(len(Data[0])): for y in range(len(Data)): if y == len(Data) -1 : dot = '\n' else: dot =' ' print(Data[y][i], end=dot) #分支算法执行类 class Worker: maxi = 0 #上界通过贪心算法找出近似值 pt_nodes = [] #存放可扩展的节点 pt_flag = 0 #标记队列是否被使用,用于结束算法 n = 0 #数据矩阵的大小 n*n min_leaf_node = None #消耗最小的叶子节点 #初始化 def __init__(self, matrix): self.n = len(matrix) self.get_up_limit() #贪心算法获取花费时间的数据上界 def get_up_limit(self): #初始化n个作业被分配情况 worker_mark = [0] * self.n for i in range(self.n): worker_mark.append(0) #利用贪心算法，从第1个作业开始寻找到完成它花费时间最少的工作人员，并记录，最终取得近似最优解 for i in range(self.n): #循环遍历n个作业 temp = matrix[i] #获得第i个作业被不同的n个工作人员完成的时间数组temp min_cost = float("inf") #初始化最小时间为inf index = 0 #初始化第i个作业未被分配 for k in range(self.n): #循环n个工作人员，找到完成作业i时间最小的工作人员 if worker_mark[k] == 0 and min_cost > temp[k]: #如果第k个工人未被分配作业并且第i个作业被第k个人员完成的时间小于最小时间时 min_cost = temp[k] #将当前完成时间赋给最小时间值 index = k #记录第i个作业被第k个工人完成获得当前最小时间花费 worker_mark[index] = 1 #标记被分配作业的工作人员k self.maxi += min_cost #累积计算上限值 #队列式（FIFO）分支界限算法,得到并输出最终结果 def branch_limit(self): for i in range(self.n): #循环n个工作人员 time = matrix[0][i] #得到第i个工作人员完成不同作业的时间 if time <= self.maxi: #如果完成时间小于最大值 node = Node() #则创建节点 #初始化节点 node.deep = 0 node.cost = time node.worker = i self.pt_nodes.append(node) #将节点放入队列 while (1): if len(self.pt_nodes) == 0: #如果队列为空 break #结束循环 temp = self.pt_nodes.pop(0) #队列非空，则遵守先进先出，弹出一个节点 present_node = temp #将当前节点看作父节点 total_cost = temp.cost #获得遍历至当前节点的总时间花费 present_deep = temp.deep #得到当前节点的深度 #初始化工人分配标记数组 worker_mark = [] for i in range(self.n): worker_mark.append(0) #检查本节点下的作业分配情况 worker_mark[temp.worker] = 1 #将被分配的工人标记为1 while temp.father is not None: #如果当前节点有父节点 temp = temp.father #则取出当前节点的父节点 worker_mark[temp.worker] = 1 #将父节点的标记置为1 if present_deep + 1 == self.n: #如果遍历深度达到n if self.min_leaf_node is None: #遍历至最后一个叶子节点不存在 self.min_leaf_node = present_node #则取当前节点为叶子节点 else: if self.min_leaf_node.cost > present_node.cost: #如果叶子节点时间花费大于父节点 self.min_leaf_node = present_node #则取父节点为叶子节点 else: #否则获取当前节点的子节点 children = matrix[present_deep + 1] #检查本节点的子节点是否满足进入队列的要求 for k in range(self.n): if children[k] + total_cost <= self.maxi and worker_mark[k] == 0: #如果时间花费小于最小值，并且第k个人未被分配工作 node = Node() #则创建节点 node.deep = present_deep + 1 node.cost = children[k] + total_cost #将当前时间加上总时间花费计入新的创建节点中 node.worker = k #添加节点参数 node.father = present_node #添加节点父节点 self.pt_nodes.append(node) #将节点放入队列 #输出算法执行的结果 temp = self.min_leaf_node print('\n总花费时间最短为：\n' + str(temp.cost) + '\n工作分配如下所示：') print('第'+str(temp.worker+1) + '位工人被分配了第'+str(temp.deep+1) + '份工作') while temp.father is not None: #如果存在父节点 temp = temp.father #返回父节点 print('第' + str(temp.worker + 1) + '位工人被分配了第' + str(temp.deep + 1) + '份工作') #分支节点类 class Node: def __init__(self): self.deep = 0 #标记该节点的深度 self.cost = 0 #标记到达该节点的总时间花费 self.father = None #标记该节点的父节点 self.worker = None #本节点的该任务由第几位工人完成 file_name = ['input_assgin05_01.dat','input_assgin05_02.dat','input_assgin05_03.dat', 'input_assgin05_04.dat','input_assgin05_05.dat'] for file_name in file_name: a = np.loadtxt(file_name) #读取存数文档 n = int( a[0][0] ) #读取小区数目 matrix = [[0 for col in range(n)] for row in range(n)] #初始化存储作业人员完成作业的时间花费 #存储作业人员完成作业的时间花费至二维数组p中 for i in range(n): for j in range(n): matrix[i][j]=a[i+1][j] print('\n###############################') print ('{0}文件中的测试结果：'.format(file_name)) print('\n'+str(n)+'个工人完成'+str(n)+'个作业的时间表为：') printTable(matrix) # 初始化算法执行类 worker = Worker(matrix) # 执行分支界限算法 worker.branch_limit() os.system("pause")