工序安排的图论模型与算法实现.docx

摘要:工序安排问题，简单的说就是通过计划、科学的安排工作，使得工作效益最大化。工序问题存在于生活的方方面面，如产品的生产流程，课程教学的编制等，基于工序安排研究范围广泛，本文将重点对本班专业的教学计划进行研究。

由于近年来学院专业课程呈现多样化和复杂性，教学计划制定也变得更加困难。目前各专业开设的课程往往是预先确定好的，各门课程间有的是相互独立，而有的课程则是有着先修后修的限定，合理的对课程排布将成为计划教学的一个关键性问题。

本文将对本专业的几门课程成绩进行统计分析，通过建模找到课程间的关联性，对所学课程进行系统排布，并根据与各学期学校专业的课程排布进行对比和可行性分析，找到最为合适的课程排布，用高级编程语言实现算法。对教学课程安排的研究，还得掌握相关的基础理论知识，如AOV网、AOE网、关键路径和拓扑排序等。

关键字：拓扑排序；AOV网；AOE网；关键路径；课程排布

目录

摘要

Abstract

1.前言-1

1.1研究背景-1

1.2研究意义-1

2.算法分析设计-2

2.1算法设计及理论依据-2

2.2学生成绩数据的建立-2

2.2.1成绩表格的建立-3

2.2.2位图-4

2.3有向图的构造-5

2.4采用邻接列表存储图-6

2.5关键路径-6

3.程序设计-8

3.1设计程序的目的-8

3.2算法设计-8

3.2.1提出问题-8

3.2.2提出假设-8

3.2.3算法求解-9

3.3程序流程图-9

4.程序源代码-10

4.1开始界面-10

4.2输入顶点数和有向边数-10

4.3输入顶点-11

4.4输入弧头、弧尾和权值-11

4.5运行结果-12

5.总结-13

参考文献-13

附录-15

致  谢-25