基于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.

作者簡介：酈莎莎 ；單位：浙江師范大學；郵寄地址：浙江省金華市婺城區浙江師范大學