基于0—1规划在零件加工问题上的应用

[摘 要]车间是生产过程中每个零件在车间内要经过某几个工序的加工，因此车间的作业计划中工件加工的排序问题是一个难点。本文通过确定优化目标，建立0-1规划模型，找出零件加工的最优排序。

[关键字]零件加工 0-1规划 最优排序

一、问题综述

某工厂的一个车间有一台高质量、高精度的机床，现有10种零件同时要求加工，如果这10种零件先在车床上车削，然后再在钻床上钻孔，加工所需时间如表一所示；应按照怎样的顺序来安排10个零件的加工顺序，才能使这10个零件在车间停留的平均时间最短？

表一

二、模型建立

该问题中零件的加工分两个工序完成，零件必须先在车床上进行车削，然后再在钻床上钻孔，故每个零件的停留时间即为其完成钻床的加工后的时间。根据总时间的定义，某零件从任务开始时刻起到完成钻床工序止所需要的总时间T包括该零件完成车床工序的时间T■，等待上一个零件加工完的时间T■以及该零件在钻床上加工的时间T■。

假设第i号零件在车床加工所需时间为P■，在钻床上加工所需时间为P■，引入0-1变量x■，则第j个零件在车床上的加工时间为：A■=■x■p■，；第j个零件在钻床上的加工时间为： A■=■x■p■，从而第j个零件完成在车床上的加工的总时间T■■为■A■，完成在钻床上加工的总时间T■■=■A■+■x■p■■+T■。 对于T■■这里要分情况进行分析： （1）当j=1时，T■■=0；（2）当j>1时，① 当T■≥T■时，此时该零件不需要等待上一个零件就可以立即进行钻床加工，因此第j个零件等待钻床工序的时间为0；② 当T■

最终即可得到如下线性规划模型：min■T■■=■■■x■p■+■■x■p■■+■max0，T■-T■■

stx■+x■+…+x■=1？噎x■+x■+…+x■=1x■+x■+…+x■=1？噎x■+x■+…+x■=1x■∈{0，1}

三、模型求解

根据所建0-1规划模型，以及已有数据，进行计算变量x■x■x■x■x■x■x■x■x■ 的值为1，其余皆为0，即所有个零件的加工顺序为：J■ ，J■ ，J■ ，J■ ，J■ ，J■ ，J■ ，J■ ，J■ ，J■ （J■表示零件i），总加工时间的最优值为：128.5h，故其平均停留时间为12.85h。

四、模型应用

本模型还可推广的n个零件在m台机器上加工排序问题，总之，通过对零件加工排序问题建立了线性规划模型，找出了目标函数，并根据加工情况给出了约束条件，使解决问题的变得简单易懂。

参考文献：

[1] 周维，杨鹏飞. 运筹学， 北京：清华大学出版社， 1990.

[2] 谢金星. 优化建模与LINDO/LINGO，北京：清华大学出版社， 2005，7.

作者简介：郦莎莎 ；单位：浙江师范大学；邮寄地址：浙江省金华市婺城区浙江师范大学