基于工期求解的排序模型算法设计与实现

摘要：在任意M×N流程调优排序模型的产品加工顺序已确定之前提下，通过分析其加工时标流线图的结构特征，进而提出了基于表格数据的总工期求解递推算法，并基于标准C完成了该算法的仿真实现，自动绘制了时标流线图，还考虑了模型数据的随机生成和对现成模型数据的读取并求解等内容。该算法简洁、明快、可操作性极强，且不受模型规模之限制，时间复杂度为O（n2）。

关键词：网络规划；时间间隔；工期；时标流线图；算法；仿真实现

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）18-4280-04

The Algorithm Design and Implementation of sorting Based on the Time Solving

CAO Ying-huai

（China Maritime Police Academy， Ningbo 315801， China ）

Abstract： In any M x N process optimization scheduling model of product processing sequence identified premise， through the analysis of the processing time scale chart structure characteristics， then based on the tabular data total time solving recursive algorithm， automatic drawing of timing chart Based on standard C completed the simulation algorithm， also consider the model data randomly generated and ready-made model data to read and solving etc.. The algorithm is concise， sprightly， extremely strong maneuverability， and not affected by scale models of the restrictions， the time complexity is O（N 2）

Key words： graph planning； time interval； construction period； timing chart； algorithm； simulation

网络规划中的M×N排序问题应用十分广泛，当工序道数M≤2时通过约翰逊定律即可轻松求解，但M≥3时常用的分组法或分界法仅可得到近优解，这也成了运筹学领域中的一个热点问题，即排序问题[1]。

虽然确定N个产品之加工顺序是排序问题的关键，但顺序确定后的工期TKW求解在目前尚无有效算法，一般通过绘制时标流线图，再从图上数出TKW值，显然这是个近乎手工的处理方法。该方法在分组（界）法中使用频繁，工作量可观。当排序模型规模较大时，绘图本身就不太现实，编程固然可行，但不是对每个人都适用[2]。

本文正是针对该状况，通过分析时标流线图的结构特征，提出了基于产品加工顺序确定时直接从原始数据表上求取工期TKW的算法，并完成了基于标准C的算法仿真实现。

1 基于间隔时间的工期求解

属于多项式级别，效果理想。

该算法的可操作性很强，在给定的表上即可直接处理，基本不受m和n的限制。

不过，局限在于各产品的加工顺序必须确定，所以，结合分组（界）法处理效果更佳，可使分组法走向实用。

当然，结合穷举N件产品的全排列，对于任意的在线排序模型来说，这也不失为求最优解的一种可行的算法[4]。

5 基于标准C的算法仿真实现[5]

5.1 之所以基于标准C

本实现的算法实现之所以基于标准C，主要是基于以下想法。尽量侧重于算法实现的细节描述，无须过多地关注模拟仿真界面的设计（诸如视窗、对象和事件等）和效果等其他因素。在尽可能短的论文篇幅里给出尽可能详尽的源程序代码。标准C可适应尽可能大的读者群体，不论是熟悉C++、VC还是C#的读者，均可直接引用之。而且，标准C与目前绝大多数院校的教学内容相一致。

5.2 算法实现的参量指标

本次实现取M≥3。同时，基于教学过程中的模拟仿真之现实，一般无须太大规模的模型描述，故仅考虑M≤100。考虑尽量简洁的仿真直观性视觉要求，时标流线图的颜色并未做区别处理，依然采用标准的黑白效果。

另外，对排序模型数据也做了一定的限制，仅考虑整型值（int）。实用中如果有浮点需求，可通过调整数据量化的单位来灵活处理，并不影响该算法的实质。

加工时间不可能出现负值，但可以为零，这也是现实情况决定的[6]。

鉴于视觉效果的考虑，本实现通过自动随机产生出的排序模型数据限定在[5，40]区间中，当然，若读者有具体的排序模型要借助该程序来求解，本实现亦支持。

通过系统随机产生的排序模型数据亦可保存在指定的磁盘文件当中。保存的模型数据采用文本文件，首行即M和N的值，后面是各道工序上各零件之加工时间。

各零件在每道工序上的加工时间，在仿真实现时以屏幕象素为单位展开，因此，当M、N较大时，TKW可能超出屏幕的显示范围。

标准C的图形显示模式支持的最大分辨率是640×480，所以，如果TKW超过了该范围，作为仿真实现而言，针对该算法源程序的简单性来考虑，此时已失去了课堂教学之需求范畴，故本实现不再研究对其时标流线图的左右拖动和缩放等功能。endprint

5.3 标准C的图形模式

基于图形模式做仿真设计是很自然的选择，而标准C的视觉效果相对于C++和VC相对较弱。另外，一般的C语言教材均很少介绍图形设计方面的内容，这便在一定程度上增加了设计的难度。图形模式设置可通过函数initgraph（）完成，再通过graphresult（）函数探测设置是否成功。图形绘制完成后，用 closegraph（）在关闭图形模式的同时，将自动释放其占据的内存资源。另外，基于象素定位的文本输出函数outtextxy、类型转化的*itoa，以及在本实现中使用较多的line、putpixel等，因相对简单不再赘述。

5.4 空间复杂度与时间复杂度的平衡

基于程序简洁性和运行效率等诸多考虑，本实现做了大量的技巧性处理，将其中“间隔时间”的计算、TKW递推求解处理等环节融合在一起，并将求解计算与流线图绘制融合在一起，这也是基于运行过程中的空间优化需求。

6 算法仿真实现的效果分析

实现中的溢出含义[7]有二，一指流线图超出屏幕边界，二是指在求解过程中，当模型规模较大时，因变量数据类型的限制而产生的溢出。对于前者，经笔者多次运行比较，一般当M≤15、N≤8时，视觉效果良好。对于后者，当M≤150、N≤150时程序运行正常，而超出该范围时程序的稳定性不良，有时会出现因内存不足而无法装载图形驱动的现象，扩充内存后效果良好。鉴于篇幅所限，程序运行时的时标流线效果图从略。

参考文献：

[1] 胡运权.运筹学[M].2版.北京：清华大学出版社， 1990.

[2] 许创杰.军事运筹学[M].1版.北京：国防大学出版社， 1998.

[3] 曹迎槐.M×N在线排序模型之工期求解算法分析[J].公安海警学院学报， 2012（1）.

[4] 曹迎槐.排序模型之TKW递推算法研究[C].管理科学与系统科学研究新进展，2003： 19-23.

[5] 曹迎槐.基于标准C的排序模型工期算法仿真实现[J].公安海警学院学报， 2012（3）.

[6] 浦在明.网络法基本原理及其应用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.运筹学与实验[M].北京：电子工业出版社，2008.endprint

5.3 标准C的图形模式

基于图形模式做仿真设计是很自然的选择，而标准C的视觉效果相对于C++和VC相对较弱。另外，一般的C语言教材均很少介绍图形设计方面的内容，这便在一定程度上增加了设计的难度。图形模式设置可通过函数initgraph（）完成，再通过graphresult（）函数探测设置是否成功。图形绘制完成后，用 closegraph（）在关闭图形模式的同时，将自动释放其占据的内存资源。另外，基于象素定位的文本输出函数outtextxy、类型转化的*itoa，以及在本实现中使用较多的line、putpixel等，因相对简单不再赘述。

5.4 空间复杂度与时间复杂度的平衡

基于程序简洁性和运行效率等诸多考虑，本实现做了大量的技巧性处理，将其中“间隔时间”的计算、TKW递推求解处理等环节融合在一起，并将求解计算与流线图绘制融合在一起，这也是基于运行过程中的空间优化需求。

6 算法仿真实现的效果分析

实现中的溢出含义[7]有二，一指流线图超出屏幕边界，二是指在求解过程中，当模型规模较大时，因变量数据类型的限制而产生的溢出。对于前者，经笔者多次运行比较，一般当M≤15、N≤8时，视觉效果良好。对于后者，当M≤150、N≤150时程序运行正常，而超出该范围时程序的稳定性不良，有时会出现因内存不足而无法装载图形驱动的现象，扩充内存后效果良好。鉴于篇幅所限，程序运行时的时标流线效果图从略。

参考文献：

[1] 胡运权.运筹学[M].2版.北京：清华大学出版社， 1990.

[2] 许创杰.军事运筹学[M].1版.北京：国防大学出版社， 1998.

[3] 曹迎槐.M×N在线排序模型之工期求解算法分析[J].公安海警学院学报， 2012（1）.

[4] 曹迎槐.排序模型之TKW递推算法研究[C].管理科学与系统科学研究新进展，2003： 19-23.

[5] 曹迎槐.基于标准C的排序模型工期算法仿真实现[J].公安海警学院学报， 2012（3）.

[6] 浦在明.网络法基本原理及其应用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.运筹学与实验[M].北京：电子工业出版社，2008.endprint

5.3 标准C的图形模式

基于图形模式做仿真设计是很自然的选择，而标准C的视觉效果相对于C++和VC相对较弱。另外，一般的C语言教材均很少介绍图形设计方面的内容，这便在一定程度上增加了设计的难度。图形模式设置可通过函数initgraph（）完成，再通过graphresult（）函数探测设置是否成功。图形绘制完成后，用 closegraph（）在关闭图形模式的同时，将自动释放其占据的内存资源。另外，基于象素定位的文本输出函数outtextxy、类型转化的*itoa，以及在本实现中使用较多的line、putpixel等，因相对简单不再赘述。

5.4 空间复杂度与时间复杂度的平衡

基于程序简洁性和运行效率等诸多考虑，本实现做了大量的技巧性处理，将其中“间隔时间”的计算、TKW递推求解处理等环节融合在一起，并将求解计算与流线图绘制融合在一起，这也是基于运行过程中的空间优化需求。

6 算法仿真实现的效果分析

实现中的溢出含义[7]有二，一指流线图超出屏幕边界，二是指在求解过程中，当模型规模较大时，因变量数据类型的限制而产生的溢出。对于前者，经笔者多次运行比较，一般当M≤15、N≤8时，视觉效果良好。对于后者，当M≤150、N≤150时程序运行正常，而超出该范围时程序的稳定性不良，有时会出现因内存不足而无法装载图形驱动的现象，扩充内存后效果良好。鉴于篇幅所限，程序运行时的时标流线效果图从略。

参考文献：

[1] 胡运权.运筹学[M].2版.北京：清华大学出版社， 1990.

[2] 许创杰.军事运筹学[M].1版.北京：国防大学出版社， 1998.

[3] 曹迎槐.M×N在线排序模型之工期求解算法分析[J].公安海警学院学报， 2012（1）.

[4] 曹迎槐.排序模型之TKW递推算法研究[C].管理科学与系统科学研究新进展，2003： 19-23.

[5] 曹迎槐.基于标准C的排序模型工期算法仿真实现[J].公安海警学院学报， 2012（3）.

[6] 浦在明.网络法基本原理及其应用[M]. 北京：金盾出版社，1995.

[7] 薛毅，耿美英.运筹学与实验[M].北京：电子工业出版社，2008.endprint