排序问题之时标流线图绘制仿真实现

摘要：在排序问题（Sequencing Program）中，当工序道数M≥3时，计算总加工时间常用的方法便是绘制时标流线图，但在教学过程中手工绘图相对烦琐，因此，笔者开发的网络规划仿真模块不仅实现了时标流线图的自动绘制，而且形象直观，经教学实践，效果良好。

关键词：排序问题;工期;时标流线图;模拟仿真

Abstract： During the sorting problem （sequencing program），And when the number of steps m≥3，The common way to calculate the total processing time is to draw the time scale streamline diagram. But in the process of teaching， manual drawing is relatively cumbersome. Therefore， The network planning simulation module developed by the author not only realizes the automatic drawing of time scale streamline diagram. And the image is intuitive， through teaching practice， the effect is good.

Key words： sequencing problem; time limit for a project; Timeline Flow Chart; analog simulation

流程调优又称排序问题（sequencing program），亦称工件加工安排问题，是一类典型的组合优化问题，它一直是运筹学研究的热点和难点之一。N个产品在M道工序的加工排序问题之M×N模型，当各产品加工次序相同时称流水作业，当各产品之加工次序不同时也称加工作业，显然流水作业是加工作业的特殊情况。虽然当M=2时，通过约翰逊定理可得最优解，但当M≥3时该问题却是典型的NP问题[1]，目前尚无最优解求解算法。

1 流程调优

虽然约翰逊定理号称解决了M=2时的排序问题，但他给出的只是产品的最优加工顺序，并未对最后的总加工时间作出公式性结论，实用中需通过手动绘制时标流线图来计算总工期。笔者曾给出了基于给定加工顺序时的表上工期递推算法[2]，但计算相对复杂烦琐，并不利于课堂教学。考虑教学过程中对排序问题求解算法原理的形象和直观性要求，笔者在开发《军事运筹学原理仿真模拟系统》（已获软著登记）时针对流程调优中的时标流线图也做了专门设计，后经教学实践，效果良好。图1即“流程调优”模块的操作主界面。

其中的“M×N模型”按钮和“1×N模型”按钮分别维护的两种模型的具体加工数据，因在1×N模型中，关注的角度一般不再是总加工时间，而是诸如平均等待时间之类的转换思路[3]，所以，单独设置了操作界面。当M=2时，可以利用图1中的“约氏解法”模拟约翰逊定律之求解示意，鉴于本文的重点是时标流线图，故这里对“约氏解法”不再做详细说明。基于同样的原因，本文也不再对“分组法”“分界法”和“穷举法”逐一介绍。

2 M×N模型之时标流线图

在图1所示之操作主界面中，单击“M×N模型”按鈕即可打开该子模块[4]，如图2。

M×N排序模型比较复杂。其模型规模，即M和N的值，可通过图1中的“设置”命令按钮来设定（细节从略），图2即6道工序（M=6）、8个产品（N=8）时的模型状态示意。当然，图中的数据是通过随机模式自动产生的，亦可手动维护之[5]。其实，使用中亦可通过“导入”命令按钮将以前保存的模型数据导入当前系统，亦可将当前的模型数据“保存”起来以备后用。模型数据维护完备后，单击图1中的“流线图”命令按钮，即可自动绘制当前M×N排序模型以当前默认的产品加工顺序时的时标流线图，图3所示就是一个6道工序7个产品的时标流线图绘制结果。

时标流线图绘制完成后，可通过屏幕左上角的三组蓝色箭头，对流线图做适当处理，诸如平移、拉伸和压缩等操作。当鼠标移动到“工期”文本框时，当前模型对应之总加工时间即显示出来，如图4。

3 时标流线图设计与实现

为尽量满足仿真的实用性，考虑仿真软件的最大产品数为50，最大工序数为20，加工时间取值范围为1-50。为方便后面对各时标流线的灵活控制或处理，还设置了移动、拉伸、压缩等诸多操作。将每个产品对应之每道工序的加工时间都用一个线性控件来表示。绘制时标流线图之前，须根据当前排序模型的实际状态，提前计算并设置（或显示）流线图坐标之水平标尺线（像素点），而纵坐标始终在框架高度之中间（像素点），横向从左边界开始至框架右边界。每隔一个时间单位（可在“设置”模块中灵活改变）做标记。其对应部分VB代码如下：

接着还需计算当前排序模型对应之各示意流线的坐标（像素点）。先计算第一项产品之第一道工序对应的流线坐标，再计算第一道工序上所有产品对应的流线坐标（第一个产品除外，它已经赋值），还得计算第一个产品在各道工序上加工时，对应的流线坐标（第一道工序除外，它已经计算完成），最后计算当前排序模型中，第2道工序及其以后的，从第2个产品开始的所有加工时间对应之流线，以及各分隔线，即第一道工序中各产品之分隔线、各道工序最后一产品之分隔线等内容。

当然，以时标流线图绘制为基础，结合分组和分界等算法，考虑教学过程中小规模模型穷举仿真之可能性，当可轻松解决M≥3时该排序问题的最优解分析，但限于篇幅，暂且从略。

因水平所限，不妥和错误之处，敬请大家批评指正！

参考文献：

[1] 钱颂迪.运筹学[M].北京：清华大学出版，1993.

[2] 曹迎槐.基于工期求解的排序模型算法设计与实现[J].电脑知识与技术，2014，10（18）：4280-4283.

[3] 曹迎槐，尹健，梁春美.军事运筹学[M].北京：国防工业出版社，2013.

[4] 曹迎槐，张静，赵强.矩阵对策之降阶算法设计与实现[J].信息系统工程，2020（10）：121-122.

[5] 曹迎槐.LP模型标准化教辅软件设计与实现[J].电脑知识与技术，2018，14（17）：87-88.

【通联编辑：谢媛媛】