An Evolutionary Algorithm for Optimal Multiple Project Scheduling

摘要

随着现代软件工程的飞速增长，对软件产品的能否具备竞争力来说无疑是一种挑战。与此同时，如何有效的确定软件项目的截止日期以及如何控制项目的成本，已成为越来越受重视的研究问题。迄今为止，在实际应用中，很少有方法能支持工程管理人员对软件项目高效进行管理，比如通过对项目任务的仿真和优化预测合理的项目截止日期。软件开发项目依靠仔细规划的时间表，然而，再详细的时间表也不能免除项目管理员因为人类固有的局限性所造成的错误判断。项目管理者必须考虑应如何在需求和突发时间中做出权衡才能实现利益最大化与代价最小化。
　　本文描述了一个多目标的多项目调度的解决方案。用来在软件生命周期中，支持项目经理最优的安排项目资源，分配项目任务，满足项目需求。软件项目生
　　命周期中存在三个优化目标。这三个目标分别是：
　　第一，通过减少生产的缺陷最大化软件产品的质量。在我们的模型中，我们认为，导致更高的软件开发时间和维修费用的软件项目的生产的缺陷需要由开发人员通过返修来解决。提高产品质量的影响被认为与不同方面的项目成果相关。
　　第二，为了评价项目完工时间，一份完善的软件开发进度时间表是必备的。对于项目中的每个模块，每项活动的具体时间被计算并且各模块的最长时间决定了项目完工时间。
　　第三，最小化工程造价。工程造价应该正比于为每个任务付出的努力，可以用每个活动所需的总时间乘以单位时间的成本来测量。软件项目成本决定了该软件在软件市场中的成功率和竞争力。
　　项目时间表的主要目的是给出合适的“脉络图”，以便协助项目管理者有效地完成该项目。项目管理者制定的时间表用来反映该项目要如何实现以及正确反应项目开发过程中的变化。项目进度计划阐明了要做的任务和活动，谁将承担这些任务（资源），什么时间应该完成（项目时间）。在实际项目开发过程中，项目进度时间表被用来监管项目进度，指定项目何时开始，何时完成该项目，以及如何合理的进行资源分配。
　　近年来，为提高对软件项目过程的认识和调度，建立了最优化模型。使用优化模型进行项目管理引入的一个具有挑战性的问题是如何支持项目管理者最好地安排项目资源和任务，以满足项目约束条件和要求。
　　我们旨在为每个项目任务设计最有效的开发方案，在增加产品质量的同时能够减少项目工期和成本。我们设计的模型包括编码、检查、测试、返修操作等几个阶段，同时也包括将项目任务分配给开发者生成项目进度表。
　　一般情况下，一个给定的软件项目的时间安排是一个由项目管理者手动建立的任务。制定项目进度计划需要耗费大量的时间、精力，并且还需要具备关于可用资源的知识以及项目进度安排的经验。然而，这项任务并没有完全摆脱由于管理者的局限性做出的错误决策，如缺乏对组织目标和资源的知识，基于不正确的假设的决策等等。一个完善的项目日程可以用于预测何时能完成项目活动。此外，它允许项目管理者查看项目的性能，并使用这些数据更精确地展望预期的工作。然而，建立一个准确和可实现的项目时间表是开发一个项目的关键活动之一。同样，定期更新和维护项目进度，以此来跟踪正在执行的项目进度也是非常重要的。考虑到人工开发调度的必要性以及它存在的缺陷，找到另一种方法在设计项目进度的早期阶段用以协助管理人员是十分有价值的。
　　在此前提下，我们提出了一种制定软件项目中的超时计划。因为在软件工程中难免会出现超时的现象，这会影响到开发者，甚至会导致软件成本和软件缺陷增加。对此，我们评估了额外的开销和超时时间。为了解决这一问题，我们采用多目标遗传算法，对项目质量、成本、工期和开发技能，以目标函数的形式，优化各个方面调度和人事安置。MOEA/D-DE我们的工作中被使用，它对复杂帕累托形状集合的多目标优化问题表现良好。我们改进 MOEA/D-DE算法用以开发软件项目时间表。算法包括遗传算法的标准程序，它包含：创建初始种群、表示不同的人口的个体、选择适者生存的个体、应用个体配偶的交叉操作和在产生孩子中应用变异算子。
　　那么，我们如何进行一系列的计算实验来评价多目标模型和分解的启发式算法呢？如何呈现我们是如何实施和执行优化模型和算法呢？为了回答这些问题，我们确定了单一的仿真运行的平均运行的时间和总的运行的时间。
　　在本论文中实现对多个软件项目进行调度的问题，该方法旨在软件项目调度的早期阶段协助项目管理者进行软件开发的时间表的指定。我们把调度多个软件项目的问题当作多目标问题，实现对软件项目的最佳调度，以达到提高产品质量的目的。同时也尽量减少项目完工时间和成本。这项研究将评估软件项目中的调度过程。
　　我们设计两种不同类型的实验进行分析。实验目的包括三个方面：第一，探讨多目标模型和提出的MOEA/D-DE算法在解决多项目调度问题的效率；第二，研究不同开发人员在设计的项目时间表方面的技能；第三，通过加班，说明软件项目成本和项目完工时间之间可能的权衡。
　　描述如何评价多目标模型和算法。此外，我们对得到的结果进行审查和分析。相信本文的研究成果为软件项目的开发添加了一个有效的工具。最后，提出对后续研究问题展望和本文涉及的几个问题的扩展与延伸。
　　在所提出的问题中，考虑到优化目标，将最高效的人力资源集合分配给每个项目活动，目的是为了最小化目标函数。所提的模型包括编码、检验、测试和重做操作阶段，并涉及到可用的开发人员所需任务的分配用以生成项目日程。在这项工作中，三个目标已经得到解决。

目录

封面

声明

DEDICATION

英文摘要

中文摘要

目录

CHAPTER 1:INTRODUCTION

1.1 Background and Motivation

1.2 Evolutionary Algorithm for Multiobjective Optimization

1.3 Main Objectives of this Thesis

1.4 Thesis Structure

CHAPTER 2:OPTIMIZATION PROBLEM

2.1 Introduction

2.2 Definition of Optimization Problem

2.3 Evolutionary Algorithms

2.4 Genetic Algorithms

2.5 Multiobjective Optimization

2.6 Summary

CHAPTER 3:LITERATURE REVIEW

3.1 Introduction

3.2 Project Scheduling Problems

3.3 Software Project Schedule Risk Management

3.4 Evolutionary Algorithms Role in Project Scheduling

3.5 Multiple Project Scheduling

3.6 Summary

CHAPTER 4:PROBLEM FORMULATION

4.1 Introduction

4.2 Objectives Description

4.3 Software Product Quality

4.4 Project Makespan

4.5 Project Cost

4.6 Overtime Planning

4.7 Summary

CHAPTER 5:MULTIPLE PROJECT SCHEDULING VIA MOEA/D-DE

5.1 Introduction

5.2 MOEA/D-DE Structure

5.3 Representation

5.4 Fitness Function

5.5 Initialization Population

5.6 Selection Operator

5.7 Crossover Operator

5.8 Mutation Operator

5.9 Summary

CHAPTER 6:EXPERIMENTAL RESULTS

6.1 Introduction

6.2 Experiments

6.3 Execution of Experiments

6.4 Varying Developers’ Skills

6.5 Summary

CONCLUSION AND FUTURE WORK

致谢

参考文献