综合实验实验报告.doc

综合实验实验报告.doc个人整理精品文档，仅供个人学习使用
综合实验实验报告
：
厦门大学计算机科学系级四班
一． 问题描述：
算法的综合应用
问题描述：
有台不同的机器， 个不同的工件。 每个工件有多道工序， 每道工序由指定的机器在固定的时
间内完成。 一道工序一旦开始处理， 就不能中断。 每台机器一次只能处理一道工序。一个调
度就是决定每台机器上工序的处理顺序， 使得机器完成所有工件的时间最短。 具体的， 该问
题就是要求在满足（） 、（）两个约束条件的前提下，确定每台机器上工序的顺序，使加工的
时间跨度（从开始加工到全部工件都加工完所需要的时间）达到最小。其中， （）表示工件
约束条件：对每个工件而言，机器对它的加工路线是事先确定的； （）表示机器约束条件：
对每台机器而言，一次只能对一道工序进行加工。
要求：
利用所学的算法求解该问题 ,任给一个输入实例，能输出最短时间以及每台机器上工序
的加工顺序。
能设计出一个用户界面。
二．
算法思路：
原先考虑过用回溯法进行解体，
解空间树是所有工件的所有工序的一棵排列树，
但这
样如果没有好的剪枝函数是不可能实现的，因为这样实现的话时间复杂度将是
(^), 其中为机
器数， 为工件数， 题目能用的剪枝函数的设计是每个工件的加工次序是有要求的，
个人预测
需要用到线性规划的内容，最后没有如此实现。
本程序使用贪心算法实现， 程序所有的工件所有的工序保存在一个二维数组中，
并且
维护一个指针， 该指针每次走动一个工序时间，
这样的一次走动将产生个工序需要加工，
其
中为工件数目， 将这个工件放到相应的个机器上，
在个机器按照加工时间递增排序，
之所以
选择递增排序， 是想让每个工序尽可能快的通过他所需要的机器，
即可以让该机器上的工序
可以更快的加工， 也可以让他之后的工序可能更快的在其他机器上进行加工，
当然这样的设
计只是直观上的说明，并不能得到最优解。
程序中维护的数据结构如下图所示，共有两个，一个用来保存所有工件的所有工序，
另一个用来表示机器加工工序。
在图一中共有六个工件～以及每个工件有个工序，
图上方的箭头表示移动的指针，
每
个移动一个工序，由于图一中的数组元素结构体设计如下：
{ 机器节点定义
当前的加工的最后时间
*; 维护一个工件链表
};
因此对于每个可以加工的工序，可以直接链入图二中的链表中不需要另外申请空间。
1 / 7
个人整理精品文档，仅供个人学习使用
（ 图一）
机器
机器
机器