工程领域排班中多目标优化研究
导读：些专家系统、决策支持系统通过使用统计模型、仿真技术及数学模型的，将精确控制和经验控制相结合E. Morgado, J. Martins提出了采用局部搜索改善人工智能的方法排班问题结果的方法.由本站硕士论文中心整理。
1绪论
1.1研究背景及问题的提出
工程建设中短工期、低造价和高质量一直都是施工单位重点关注的问题。合理加快工程进度、缩短工程的施工工期，是市场经济对施工单位的要求，是满足业主方要求的必要条件，也是施工单位提高经济效益和社会效益的有效途径。由十，人力要素是在工程施工中往往更好控制，为了加快工程进度，施工管理者可以采用多种方式提高劳动时间。
使用多种班制来加速工程进度，满足工期要求，是施工方经常采用的措施。每天使用s小时的两班制或二班制有多种优点:
1)每周的工作时间成倍提高。
2)减少因为工程拖延带来的额外风险和成本。
3)减少由十工人疲劳加班带来的施工安全风险。
4)减少工作场所的交通安全风险。
5)提高设备利用率，降低设备折旧成本。
然后，工程建设中采用多种班制也会对工程成本、劳动生产率、安全带来负面影响。使用多种班制会带来额外的成本，这些成本包括额外的保险费用、晚间照明、质量控制和安全保障措施。另外，晚间工作扰乱了工人的生理节律[2]，容易降低生产效率并导致工作中的安全问题 Folkard和Tucker发现晚班是事故率高十白班班在二种班制有最高的事故率。同时，大多数员工都倾向十白班制，这又造成了工程管理安排晚班和夜班人员时面临的另一个问题。Ifn最近研究表明使用晚班和夜班工作制会导致更高的人员流失率和旷工率，从造成工期拖延和成本超支[7][8]。因此，研究使用多班制缩短工期的同时，也要尽量缩短多班制的负面影响。
多种班制也要考虑劳动力限制。因为在实际工程项目中劳动者是不应该在一天之内同时参与两种或两种以上班制的。这就要求工程计划者在有限的劳动力约束的情况下制定出最有效的人员班制及数量的分配方案。
多班制劳动力优化问题，是特殊的工程建设资源优化问题，研究多班制资源优化问题也可以为其他相似工程建设资源优化提供解决思路。
1.2排班问题的研究现状
人员排班问题通常是研究在一定约束条件下，如何安排参与人员的工作方式，以达到成本最低，效益最好的目标。软件公司、仓库保管、航空、铁路、公交、服务行业等，都迫切希一望能够有合理有效的人员安排方法。人员班制的安排考虑结合工作任务要求、工作条件及优化目标，研究的方向也多种多样。
1.2.1排班问题的分类
1)任务要求不同
呼叫中心、护士值班这样的工作要求，需要24小时安排人员在岗，同时，在工作时间内，存在任务量高峰和低谷的时段，排班的目的是更好的应对不可准确预测预测的任务量。
比如交通和服务部门，在不同时段，可能面临不同的工作任务。排班的主要目是，应对工作任务的要求，提高服务质量。在我国，当十一黄金周或是春节期间，交通部门的工作任务量急剧增加，增加班制和人员的投入，应对运输高峰。
在软件行业和工程建设中，为了加快项目进度，缩短项目周期，对十关键的项目点，加大人力，安排具备相应技能的工作人员，以保证项目在规定时间内完成。
2)排班实体不同
这里把调度的对象成为实体，可以是参与工作的个体，也可以是由个体组成班组，甚至是施工设备。在讨论排班的实体时，可以分为有差异的实体和无差异的实体。当对不同性质的工作安排实体时，考虑实体的能力能否胜任时，就要讨论实体的差异性。工作任务一样，对实体的种类不存在特殊要求时，就不需要讨论实体的差
异性。Sigrid Knust, Elisabeth Schumacher研究了小型石油公司油罐车的调度安排，由十不同油罐车有不同的操作方式，需要安排具备相应操作能力的司机。另外一种情况，在人员排班中将考虑兼职人员的排班。例如，Vakhariaetahl0}and Laueretahly研究了包括全职和兼职不同类型人员的排班问题。
3)决策变量不同
柳kin, T.等人在人员安排的研究中，将人员工作及交换班的体息和吃饭时间也引入模型中T.研究了一个工作口，如何安排各班制的人员数量及工作的起始时间及工作时间的长度和各个班制下人员的休息时间和午饭时间。
4)约束条件不同
a)资源条件的约束
如参与排班的人员人数的总数，分配给参与工作人员的设备，生产的原材料。
b)工作时间的约束
Aykin, T.在Optimal shift scheduling with multiple break windows中定义了体息时间窗的概念，指工作人员从上班开始算起，经过一个体息时间窗后才能安排人员的体息。柳kin, T.还将对时段划分了粒度，工作人员的体息时间只能发生在不同时间粒度上。
此外，班制工作时间长度也会提出要求。法律规定员工是8小时工作制，超过8小时工作时间企业必须支付加班费用。然Ifn，从工作要求或企业效益角度出发，企业也不允许员工每天的工作量低十某个限度。这样，在规划劳动者班制的工作时长时，就有了上下限的约束。
c)员工意愿和公平性约束
前面已经提到，多班制会对员工生活作息产生重大影响。一些企业为了保证多班制的顺利实施，给子员工一定的鼓励措施，在尊重员工意愿的条件下，公平的安排人员班制方案。这类约束有可能在制定方案中是软约束，因为对十公司来说，只能尽量满足员工的意愿需求，但是满足所有员工的需求也是不现实的。SrimathyMohan}l细守员工的个人偏好作为目标函数，在最小化人力成本的同时，最大化所有员工的最大偏好。
d)轮换规则的约束
考虑到劳动者体息时间、体力和心理承受能力以及参与工作的实际要求，从一个班制转换到另一班制下，需要服从一定规则。比如，从事夜班的工作人员马上又被安排在下轮的白班，这样做显然是不合理的。
1.2.2解决排班问题常用的方法
1)数学方法
Dantzig, G.B.基十覆盖集的理论，采用传统数学规划模型，去处理了人员排班的问题。由十该方法要考虑所有的可能的班制类型，班制开始时间持续时间和员工体息时间，模型中设定了大量的决策变量，使得该方法的应用受到极大限制。Mason,助an, Paton C 1998)提出基十覆盖集整数规划的分阶段排班过程规划的分阶段排班
过程[5]。大量的整数规划的方法都是基十覆盖集模型或是它的变形。
覆盖集模型可以采用精确的算法或是启发式算法求解。分支定界法师求解线性整数规划最常用的方法。在处理实际问题时，搜索分支树一般比较耗时，这时可以采用启发式的规则结束搜索。比如，找到的第一个解或是一个较好的解则终止，只固定的搜索部分变量。拉格朗口启发式算法是解决排班问题的一个非常实用并广泛采用的方法。分支切割和分支定价的方法也在处理人员排班的问题中广泛应用。
虽然这种数学规划的方法能够清晰的表述问题，但是用求解一个人员排班的问题求解相对比较困难非常耗时.即使现在的计算机性能获得，极大提升，要去求解这种几百万甚至上亿的变量，仍然不太可能，因此这些方法大多只能应用在简单的实际问题中。
2)兀启发式算法
兀启发式算法常用来处理复杂的组合优化问题。传统的启发式算法，如最速下降法、局部贪婪算法不能处理的问题可以尝试采用兀启发式算法。
兀启发式算法通常融合了不同的启发式算法。如，模拟退火算法(Simulated Annealing Algorithm，禁忌搜索算法(Tabu SearchAlgorithm)，遗传算(Genetic Algorithm，问题空间搜索，贪婪随机模拟退火算法(Greedy Random Adaptive Search Procedure，神经网络算法( Neural Networks )，机器学习(Machine Learning，强化学习(Reinforcement Learning )，蚁群算法(Colony Optimization。启发式算法的回顾可以参考文献.
3)人工智能的方法
人工智能也被用来处理人员排班的问题。在人员排班中，可能存在某些因素影响排班结果，但是很难将这些因素加入到模型中，有时使用经验知识能够更好的描述这些因素。因此采用人工智能的方法，对现有样本学习，从提出人员排班的计划。目前，常用的方法有，过模糊集理论、模糊搜索、专家系统等。
在一些，排班过程中面临不确定因素的排班问题，更加适用十采用模糊集理论的方法。Slowinski and Hapke (2000)较全面的提供了使用模糊集排班的综述，基十模糊理论的排班方法一般有两类应用:1.基十变动约束条件下的排班问题;2.基十不完全信息下的排班问题。如中采用模糊集理论，指导遗传算法在搜索解。
一些专家系统、决策支持系统通过使用统计模型、仿真技术及数学模型的，将精确控制和经验控制相结合o E. Morgado, J. Martins提出了采用局部搜索改善人工智能的方法排班问题结果的方法.
4)约束规划(Constraint programming)
约束规划，也叫约束逻辑规划(Constraint Logic Programming )，是一种约束陈述语言。算法在搜索可行解时，利用问题本身包含的信息减少搜索空间。首先确定各个变量的值域，将不可能的值去除，再通过变量之间的约束关系将变量的值域进一步缩减。在搜索的过程中，当一个变量的值域发生改变时，与之相关的信息就被调用，从更新其余变量的可选值，这就是约束传递的过程.
约束规划的方法为排班问题提供了一种较为有效的解决思路。这种方法的难点是要在大量的可行解中搜索到最优解或是近似最优解。
约束规划通常被设计成树形搜索的形式。很多组合优化模型都是NP-hard问题，如果遍历树进行搜索往往不切实际。考虑到时间限制，通常只搜索整个树的一个子集。比如深度优先搜索就常常被用来处理约束传播增加的问题。深度优先搜索中，到某个起点时就探索是否还有没有探测到的边，如果有，就沿边继续搜索下去。通常搜索树的左边底部的部分。偏好搜索([匕如[[25] >用来搜索树的局部。大部分情况下，给定时间内，局部搜索产生的解比深度搜索要好。目前，很多学者研究了局部搜索和偏好搜索结合起来混合搜索。如大型的领域搜索[[26]，这种方法是在全局搜索或局部搜索的一个领域内进行搜索。
Localizer}2}]的局u}‘搜索，Pascal Van Hentenryck的树搜索III Caseau Y SALSA提出的局部搜索和全局搜索结合的搜索都是此类问题的尝试。
此外，一些学者还将约束规划与传统的优化方法相结合。比如，采用了约束规划的方法对线性规划的上界和下界进行了预处理。文献[[31]又将约束规划和启发式算法想结合。
目前已有大量关十优化工程建设资源的研究，这些研究使用了多种优化技术，以最小化工程周期、工程成本为目标或综合分析工期成本。
Dho Heon Jun和Khaled El-Rayes详细介绍了如何处理多班制人力利用的工程建设问题。但是，并没有讨论人力数量如何在工程建设中分配的问题。这篇文章采
用遗传算法作为解决工具，因为普通遗传算法在基因片段过长时往往会陷入复杂的搜索过程中，所以该文章并没有将单独工程下、特定班制的人员数量作为决策变量.
1.3论文研究思路及框架
本文主要对多班制的工程建设问题进行探讨。具体内容如下:
第一章简要介绍了工程建设中采用多班制的意义，及相应要注意的问题。对十国内外研究的排班问题进行了分类，并总结了常用的排班中使用的方法。
第二章对提出了本文要研究的主要问题。描述了工程排班问题考虑的因素，提出了工程建设中要实现的优化目标，并详细介绍了分析问题的思路和处理方法。
第二章界定了了本文的研究范围，建立了针对工程建设多班制的多目标优化模型，并指明了模型的应用条件。
第四章详细介绍了模型的实施。分别介绍了求解模型所需的二个模块，初始化模块、排程模块和遗传算法模块。在遗传算法模块中详细介绍了了两种不同的建立种群的方式，并分别探讨了两种方式实施方法及不同。由十本文采用了改进的遗传算法，在介绍二个模块之后，又单独一节的篇幅介绍了遗传算法模块中使用的改进方法。
第五章是案例分析。以具体的工程实例进行计算和分析，验证本文中提出的模型的合理性和可行性。
第六章是模型评价，对现有模型进行了总结，并分析了不足，对后续工作提出了建议。
参考文献
1.A.S. Hanna, C. Chang, K.T. Sullivan and J.A. Lackney. Impact of shift work on labor productivity for labor intensive contractor[J]. J. Constr. Engrg. and Mgmt. 2008,134:197204.
2.夏卫.夜班倒班劳动对健康的影响[J]. Railway Occupational Safety, Health &Environmental Protection.1984,2:64}66.
3.K. Kogi. Temporal factors in work scheduling. In: S. Folkard and T.H. Monk,Editors, Introduction to the Problems of Shiftwork[J]. Hours of Work. 1985.
4.S. Folkard and P. Tucker. Shift work, safety and productivity[J]. Occup. Med.2003,53:95-101.
5.L. Guerin and A. De1Po. Create Your Own Employee Handbook[J]. A Legal and Practical Guide, CA, Nolo, Berkeley ,2007.
6.C. Czeisler, M. Moore-Ede and R. Coleman. Rotating shift work schedules that disrupt sleep are improved by applying circadian principles[J]. Science. 1982, 217: 460463.
7.J.E. Gomar, C.T. Haas and D.P. Morton. Assignment and allocation optimization of partially multiskilled workforce[J].Journal of Construction Engineering and Management. 2002,128:103一109.
8.P. Knauth. Design of shift systems for shiftwork[M]. In: W Karwowski, Editor.International Encyclopedia of Ergonomics and Human Factors, Taylor&Francis， 2001.
9.Sigrid Knust, Elisabeth Schumacher. Shift scheduling of tank trucks[J].Omega,2011,39:513}521.
10.Vakharia AJ,Selim HS,Husted RR. Efficient scheduling of part-time employees [J].Omega,1992(20):201一 213.
11.LauerJ, acobs LW, Brusco MJ, Bechtold SE. interactive, optimization-based decision support system for scheduling part-time computer lab attendants[J].Omega 1994(22):613626.
12.Aykin, T. Optimal shift scheduling with multiple break windows [J]. Management Science 1996(42):591603.
13.张双华，张晓维，高士信.建筑施工组织[M].黑龙江:黑龙江科学技术出版社.2003:1 }2.
14.林锉云，董加礼.多目标优化的方法与理论[M].吉林教育出版社，1992.910.
15.赖红松，董品杰，祝国瑞.求解多目标规划问题的Pareto多目标遗传算法田.系统工程.2003, 21(5).
16.土小平，曹立p}.遗传算法一一理论、应用与软件实现【M].西安:西安交通大学出版社，2002.6976.
17.高鹜，郭锦标，杨明诗.约束规划在原油调度中应用的探索阴.计算机与应用化学， 2006:23(12): 12391244.
摘要 4-5
Abstract 5
1 绪论 8-14
1.1 研究背景及问题的提出 8-9
1.2 排班问题的研究现状 9-13
1.3 论文研究思路及框架 13-14
2 工程建设多班制优化问题 14-19
2.1 问题描述 14-15
2.2 优化目标 15-16
2.3 模型及求解算法 16-17
2.4 本章小结 17-19
3 多目标优化模型的建立 19-24
3.1 模型界定 19
3.2 多目标优化数学模型 19-23
3.3 本章小结 23-24
4 基于多目标遗传算法的模型实施 24-43
4.1 初始化模块 24-25
4.2 排程模块 25-28
4.3 遗传算法模块 28-37
4.4 改进的遗传算法 37-41
4.5 本章小结 41-43
5 工程实例计算与结果分析 43-49
5.1 工程实例介绍 43
5.2 计算结果 43-47
5.3 结果分析 47-48
5.4 本章小结 48-49
6 总结与展望 49-50
6.1 全文总结 49
6.2 展望 49-50
致谢 50-51
参考文献 51-55
附录1 工程建设多班制数据 55-58
附录2 攻读学位期间参与的课题研究 58
您可能有工程硕士学位论文方面的购买需求，请到工程论文硕士论文频道选取：