不同交貨期時間窗下的平行機(jī)生產(chǎn)問題研究

楊婉琳，朱伏平

（西南科技大學(xué)制造科學(xué)與工程學(xué)院，四川 綿陽 621010）

1 引言

傳統(tǒng)大規(guī)模生產(chǎn)逐漸出現(xiàn)定制化生產(chǎn)需求，在有限設(shè)備生產(chǎn)能力下，合理安排生產(chǎn)任務(wù)加工，高效、及時、動態(tài)規(guī)劃生產(chǎn)排程，進(jìn)行智能化生產(chǎn)調(diào)度成為眾多企業(yè)的共同目標(biāo)。生產(chǎn)排序問題研究，按有無交貨期約束情況分為兩類：一類無交貨期約束[1-3]，另一類有交貨期約束。對于無交貨期約束情況，大部分研究者以時間表長最短、設(shè)備準(zhǔn)備時間最短、等待時間最短等作為決策指標(biāo)。如文獻(xiàn)[4]以總訂貨提前期與總成本加權(quán)和最小化作為目標(biāo)，禁忌搜索算法與動態(tài)規(guī)劃算法相結(jié)合，研究訂單分配、生產(chǎn)調(diào)度和分批運輸調(diào)度三個階段。在少量研究有交貨期約束生產(chǎn)排序問題中，研究者多以交貨期相同[5]情況作為研究對象，并假設(shè)生產(chǎn)任務(wù)是允許延誤，以最長延誤時間、總延誤時間最短[6]等作為決策變量，建立基于算法基礎(chǔ)的拖期懲罰隸屬函數(shù)等。如文獻(xiàn)[7]提出對模糊交貨期Flow-shop調(diào)度問題機(jī)會約束設(shè)置懲罰函數(shù)，引進(jìn)自適應(yīng)變異和交叉方法改進(jìn)算法；而生產(chǎn)任務(wù)交貨期限不同的平行機(jī)生產(chǎn)排序問題，目前研究較少[8-10]。研究在訂單交貨期、到達(dá)時間等約束條件下平行機(jī)生產(chǎn)排序問題，提出在準(zhǔn)時交貨條件下“最小提前生產(chǎn)時間”，解決在優(yōu)先考慮不同交貨期約束下平行機(jī)生產(chǎn)排序問題。

2 問題描述和模型建立

j個任務(wù)在m臺平行機(jī)上進(jìn)行生產(chǎn)，任務(wù)集合為J=｛J1，J2，…Jj｝，機(jī)臺集合為M=｛M1，M2，…Mm｝。m臺平行機(jī)均可加工工廠任意產(chǎn)品，由于任務(wù)數(shù)量j遠(yuǎn)遠(yuǎn)大于機(jī)臺數(shù)量m，并存在眾多不可提前預(yù)知生產(chǎn)任務(wù)加工時間區(qū)間沖突，故該類問題為NP問題。

模型建立界定范圍如下：

（1）面向訂單生產(chǎn)方式，必須保證生產(chǎn)任務(wù)在交貨期前完成，生產(chǎn)任務(wù)加工過程不可以中斷；

（2）機(jī)臺更換加工任務(wù)準(zhǔn)備時間是一個常數(shù)δ，假設(shè)時間常數(shù)δ極小于加工時間，在生產(chǎn)排序中忽略常數(shù)δ影響；

（3）該系統(tǒng)不研究沒有充足加工時間插單和急單問題；

（4）一個生產(chǎn)任務(wù)同時只可以在一個機(jī)臺上完成，一個機(jī)臺同時也只能加工一個生產(chǎn)任務(wù)；

（5）生產(chǎn)任務(wù)可以提前，但不允許延誤。

下文中使用的符號定義，如表1所示。

表1 符號定義表Tab.1 Symbol Definition Table

模型建立需滿足以下假設(shè)。假設(shè)1：每臺平行機(jī)上加工作業(yè)應(yīng)根據(jù)開始加工時間進(jìn)行不減排列，即根據(jù)EST規(guī)則進(jìn)行排列，每臺機(jī)臺上加工任務(wù)應(yīng)不存在時間競爭。假設(shè)2：每個生產(chǎn)任務(wù)都必須被完成，并且每個加工任務(wù)都應(yīng)在交貨期前完成。假設(shè)3：上述模型問題，一定存在一個或多個提前加工時間最小的最優(yōu)解。建立平行機(jī)生產(chǎn)排序求解最終模型。

式中：（1）—所有加工任務(wù)在客戶要求交貨期前完成；（3）—對于一個機(jī)臺上所有加工任務(wù)，不存在加工時間競爭；（4）—一個加工任務(wù)僅能在一個機(jī)臺上完成，并且每個加工任務(wù)都必須被機(jī)臺加工。

3 算法設(shè)計

3.1 基于“虛擬訂單”的組合策略

“虛擬訂單”假定所有產(chǎn)品交貨期一致，用于預(yù)測訂單分布，以保證在產(chǎn)品機(jī)臺組合時機(jī)臺負(fù)荷均衡化、后期數(shù)據(jù)調(diào)整快速響應(yīng)。下文中使用的符號定義，如表2所示。

以LPT（最長加工時間優(yōu)先）為規(guī)則，（20～80）%原則作為約束條件，優(yōu)化同速機(jī)不可中斷極小化表長排序問題。

目標(biāo)函數(shù)：Pm∥Cmax

（1）依排列結(jié)果進(jìn)行百分比累計，累計百分比第一次出現(xiàn)大于或等于80%時停止百分比累計，即B1+B2+B3+…+Bn-1＜80%，B1+B2+…Bn-1+Bn≥80%，B1至Bn代表n種產(chǎn)品為“虛擬”訂單中產(chǎn)品種類，得出虛擬訂單集合 X=｛X1，X2，…Xn｝，Xn=（i，Pi，Δt）。

（2）任務(wù)按加工時間 Pi進(jìn)行不減排列，即 An-1≥An，n=1，2，…n；

（3）當(dāng)t=0時，取前m個任務(wù)依次排列在m臺機(jī)臺上，機(jī)臺Mm上加工產(chǎn)品集合記為 Sm=｛a，b，…k∥a，b，…k∈（1，2，…i）｝，若任務(wù)Xn中產(chǎn)品i在機(jī)臺Mm上加工，則稱i∈Sm，Xn∈Mm；

（4）任務(wù)Xn排在機(jī)臺Mm上，則機(jī)臺負(fù)荷率Fm=Σi∈SmPi/Δt，檢驗是否Fm≥80%，若“是”則該機(jī)臺飽和，退出可用機(jī)臺集合；若“否”，則該機(jī)臺仍存在于可用機(jī)臺集合中；即：

（5）取剩余任務(wù)中加工時間最長任務(wù)（未加工任務(wù)中加工時間最長者）排在Fm最小機(jī)臺上；

（6）重復(fù)步驟（4），重復(fù)步驟（5）；

（7）直到n個任務(wù)全部排完得出機(jī)臺產(chǎn)品組合策略Dm。

表2 符號定義表Tab.2 Symbol Definition Table

3.2 加工任務(wù)在機(jī)臺的分配

任務(wù)集合進(jìn)入生產(chǎn)系統(tǒng)之后，根據(jù)機(jī)臺產(chǎn)品組合策略D_m得出機(jī)臺 m 加工任務(wù)集合 Sm=｛Ja，Jb，…Jk∥Ja，Jb，…Jk∈J｝，機(jī)臺Mm的加工任務(wù)集合中生產(chǎn)任務(wù)均屬于任務(wù)集合J=｛J1，J2，…Jj｝。設(shè)計基于ECT規(guī)則生產(chǎn)就緒時間可控提前的生產(chǎn)排序啟發(fā)式算法。

（1）生產(chǎn)任務(wù)進(jìn)入，依據(jù)產(chǎn)品機(jī)臺組合Dm進(jìn)行任務(wù)分派，在Dm中找不到生產(chǎn)機(jī)臺的生產(chǎn)任務(wù)進(jìn)入集合D中等待處理。機(jī)臺Mm上生產(chǎn)任務(wù)即Sm中Jj按照交貨期dj進(jìn)行不減排序（ECT規(guī)則），在機(jī)臺Mm上等待加工任務(wù)數(shù)記為k，排列?=（?1，?2，…?k），存在 d?（n-1）≤d?（n），n=1，2，…k。

（2）針對Sm中不減排序生產(chǎn)任務(wù) Jj，若存在任意 n 使得 d?（n-1）-d?（n）≤0，則任務(wù) J?（n）與任務(wù) J?（n+1）在機(jī)臺 Mm上存在生產(chǎn)時間沖突，故將任務(wù) J?（n+1）從機(jī)臺 Mm加工任務(wù)集合中刪除，任務(wù) J?（n+1）進(jìn)入集合 D 中等待安排。即：若 J?（n）∈Sm，則??n∈（1，2，…k）

（3）機(jī)臺出現(xiàn)（2）情況，則轉(zhuǎn)（4），若不出現(xiàn)，轉(zhuǎn)（5）。

（4）刪除重合加工任務(wù)J?（n+1）后，根據(jù) dj再次進(jìn)行不減排序。重復(fù)步驟（2）。

（5）針對機(jī)臺Mm初步生產(chǎn)任務(wù)安排完成，機(jī)臺Mm上所有加工任務(wù)均不存在時間沖突，在機(jī)臺無故障發(fā)生時候可以保證完成。整理集合D中加工任務(wù)，記集合D中加工任務(wù)數(shù)為k，則按照開始加工時間 r_j進(jìn)行不減排序（EST 規(guī)則），排列 π=（π1，π2，…πk），即存在 rπ（n-1）≤rπ（n），n=1，2，…k。

（6）依次選取集合D中按加工開始時間排序的生產(chǎn)任務(wù)Jj，在眾多機(jī)器中篩選出滿足任務(wù)Jj需求時間區(qū)間空閑機(jī)器Mm，記機(jī)臺Mm對任務(wù)Jj的接受能力為Nmj，Nmj=0可接受，Nmj=1不可接受。?Jπ（n），Jπ（n+1）∈Sm則：

（7）Nj0為任務(wù)Jj可用機(jī)臺集合，Nj1為任務(wù)Jj不可用機(jī)臺集合。，則轉(zhuǎn)至（8），若 N=?，則轉(zhuǎn)至 2.3。j0

（8）在Nmj=0可接受機(jī)臺Mm上與任務(wù)Jj開始時間rj最接近結(jié)束時間 dπ（n）生產(chǎn)任務(wù)稱為 Jπ（n），記 Δχ=rj-dπ（n）。任務(wù) Jj選擇在 Δχ最小的機(jī)臺上生產(chǎn)。即：minΔχ=rj-dπ（n），Nmj=0，Jπ（n）∈Sm?Jj∈Sm。

3.3 最小提前生產(chǎn)時間排序

（1）當(dāng)Nj0=?，無機(jī)臺可為生產(chǎn)任務(wù)Jj提供加工時間時，機(jī)臺需調(diào)整生產(chǎn)任務(wù)安排，為保證所有產(chǎn)品在交貨期前完成，將機(jī)臺上生產(chǎn)任務(wù)提前。對于任意機(jī)臺Mm上，存在加工任務(wù)Jπ（a），使Jπ（a）≤dj，Jπ（a+1）＞dj，則生產(chǎn)任務(wù) Jπ（a）和 Jπ（a+1）之間空閑時間區(qū)間 θa=［da，ra+1］，a∈［1，k］。任務(wù) Jj與任務(wù) Jπ（a）之間時間區(qū)間記為 τa，為更好解決生產(chǎn)計劃安排問題，進(jìn)行分類歸納可得出：

（2）存在一個n使

（3）任務(wù)Jj提前投入生產(chǎn)時間記為Ej，則：

Ej=Ej

Ea=dj-rj-τa

Ea-1=dj-rj-τa-θa-1

Ea-n+1=dj-rj-τa-θa-1-…-θa-n+1

Ea-n=dj-rj-τa-θa-1-…-θa-n+1-θa-n

（4）機(jī)臺Mm上加工任務(wù)提前生產(chǎn)時間總和記為Em，Em最小機(jī)臺Mm即為任務(wù)Jj加工機(jī)臺，機(jī)臺Mm上加工任務(wù)Ja最終開始加工時間

（5）得出所有機(jī)臺上生產(chǎn)任務(wù)集合Sm和生產(chǎn)計劃Smr。

4 仿真案例實踐

設(shè)計以下仿真案例實驗，用MATLAB軟件，隨機(jī)抽取5臺機(jī)臺和25個生產(chǎn)任務(wù)進(jìn)行仿真，對仿真結(jié)果進(jìn)行評價。運行環(huán)境為：Windows10 64位操作系統(tǒng)，內(nèi)存為4G。實驗包括25個生產(chǎn)樣本、5臺可供選擇機(jī)器，依據(jù)啟發(fā)式算法規(guī)則進(jìn)行仿真計算，最后輸出結(jié)果為25個樣本生產(chǎn)計劃排程以及各機(jī)臺占有率和利用率。使用上述最小提前生產(chǎn)時間算法得出生產(chǎn)排程，如表3所示。驗證機(jī)臺占用率和利用率充分說明該算法有效性和優(yōu)越性，在不接受新生產(chǎn)任務(wù)和拒絕原生產(chǎn)任務(wù)硬性條件下，通過使用該算法，降低了機(jī)臺平均占用率，提高了機(jī)臺利用率，減少機(jī)臺閑置，最大限度使用設(shè)備，各設(shè)備工作任務(wù)分配較為合理，如表4所示。

表3 生產(chǎn)任務(wù)排程Tab.3 The Production Task Scheduling

表4 算法數(shù)據(jù)對比表格Tab.4 Algorithm Data Contrast

5 結(jié)束語

研究企業(yè)在訂單交貨期、到達(dá)時間和設(shè)備產(chǎn)能資源等約束條件下平行機(jī)生產(chǎn)排序問題，以提高客戶滿意度、保證產(chǎn)品交貨期為出發(fā)點；最小化訂單提前生產(chǎn)時間作為目標(biāo)，利用啟發(fā)式規(guī)則構(gòu)建虛擬訂單進(jìn)行產(chǎn)品組合，建立基于交貨期約束系統(tǒng)求解模型；提出“最小提前生產(chǎn)啟發(fā)式算法”進(jìn)行求解，解決眾多企業(yè)在優(yōu)先考慮不同交貨期約束下平行機(jī)實際生產(chǎn)調(diào)度問題；最后，使用仿真實驗進(jìn)行模型求解，驗證了該方法可行性，以及在實際生產(chǎn)排程中優(yōu)越性，該應(yīng)用研究為進(jìn)一步研究不同交貨期時間窗下較大規(guī)模復(fù)雜平行機(jī)排序問題提供可鑒方法，填補(bǔ)交貨期約束研究下部分空缺。研究問題中尚未準(zhǔn)確考慮到緊急訂單插單排序問題、供應(yīng)鏈斷鏈等情況，這些值得更進(jìn)一步研究。