多阶段双层目标分配问题的精确算法

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (21): 44-47.

多阶段双层目标分配问题的精确算法

马芹芹，郭强，付晓薇

西北工业大学理学院，西安 710129

出版日期:2014-11-01 发布日期:2014-10-28

Precise algorithm of bi-objective assignment problem based on multi-stage

MA Qinqin, GUO Qiang, FU Xiaowei

College of Science, Northwestern Polytechnical University, Xi’an 710129, China

Online:2014-11-01 Published:2014-10-28

摘要/Abstract

摘要： 针对所有工作必须分阶段依次完成，但同一个阶段的工作可以同时进行的情况下，如何分配现有人员来承担这些工作，才能使得完成所有工作的工期最短，并在此前提下使花费的总用时最少的分配问题，通过引入立方检测矩阵，给出了一种单调下降的迭代算法。该算法不但能获取精确最优解，而且有很好的计算效率。

关键词: 分配问题, 双层目标, 立方检测矩阵, 迭代算法, 精确最优解

Abstract: All jobs must be grouped into some stages and carried out successively, but jobs at the same stage can be commenced simultaneously. In this case, this paper researches how to allocate all jobs to the existing persons so as to minimize the completion time subject to the minimum makespan. A monotone decreasing iterative algorithm, which can obtain the precise optimal solution and has good computational efficiency, is proposed by introducing cubic detection matrix.

Key words: assignment problem, bi-objective, cubic detection matrix, iterative algorithm, precise optimal solution

马芹芹，郭强，付晓薇. 多阶段双层目标分配问题的精确算法[J]. 计算机工程与应用, 2014, 50(21): 44-47.

MA Qinqin, GUO Qiang, FU Xiaowei. Precise algorithm of bi-objective assignment problem based on multi-stage[J]. Computer Engineering and Applications, 2014, 50(21): 44-47.

[1]	熊兴隆，刘佳，李猛，马愈昭. 基于无人机-配送车联合配送的优化算法研究[J]. 计算机工程与应用, 2021, 57(19): 259-266.
[2]	徐齐利. 讨价还价博弈均衡出价策略的算法设计[J]. 计算机工程与应用, 2020, 56(21): 170-175.
[3]	王茜竹1，2，李楠1，2. 大规模MIMO系统的改进RTS信号检测算法[J]. 计算机工程与应用, 2018, 54(12): 74-79.
[4]	盛昌杰1，2，韩雷1，2. 不对称光阑对相干衍射成像缺陷检测效果的影响[J]. 计算机工程与应用, 2017, 53(14): 178-182.
[5]	丁宪成. 模糊偏好关系一致性改进算法及其决策应用[J]. 计算机工程与应用, 2016, 52(24): 62-69.
[6]	李群辉 1，张俊祖1，耿国华2，周明全3. 基于凹凸区域的断裂面匹配算法[J]. 计算机工程与应用, 2016, 52(13): 187-190.
[7]	李果1，洪旭东2，许建1，黄翰2. 求解护士分配问题的矩阵编码进化算法[J]. 计算机工程与应用, 2015, 51(4): 244-248.
[8]	高磊，解培中. MIMO干扰信道中一种新的分布式迭代预编码算法[J]. 计算机工程与应用, 2015, 51(16): 77-81.
[9]	屈百达，陈龙，徐保国. 改进的时延丢包网络控制系统的分析和控制[J]. 计算机工程与应用, 2014, 50(22): 130-135.
[10]	熊邦书1，李腾1，赵平均2，史胜西1. 基于航迹可飞性改善的A*算法[J]. 计算机工程与应用, 2014, 50(19): 58-60.
[11]	王鲜芳1，杜志勇2. 利用矢量基学习和自适应迭代算法改进LSSVR[J]. 计算机工程与应用, 2012, 48(6): 38-41.
[12]	徐先峰，刘义艳，段晨东. 基于多步分解算法的解盲源分离新方法[J]. 计算机工程与应用, 2012, 48(30): 162-166.
[13]	陈虎. 基于QFD和双层规划的物流服务供应商选择研究[J]. 计算机工程与应用, 2012, 48(27): 200-205.
[14]	戴宽平，吕全义. 改进的并行Arnoldi方法[J]. 计算机工程与应用, 2011, 47(34): 72-73.
[15]	程汤培1，王群1，季晓慧1，黄林显2，徐腾2. 一种孔隙介质中地下水流并行计算方法[J]. 计算机工程与应用, 2011, 47(20): 234-237.