楊婉琳，朱伏平

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

1 引言

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

2 問(wèn)題描述和模型建立

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

模型建立界定范圍如下：

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

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

（3）該系統(tǒng)不研究沒(méi)有充足加工時(shí)間插單和急單問(wèn)題；

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

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

下文中使用的符號(hào)定義，如表1所示。

表1 符號(hào)定義表Tab.1 Symbol Definition Table

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

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

3 算法設(shè)計(jì)

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

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

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

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

（1）依排列結(jié)果進(jìn)行百分比累計(jì)，累計(jì)百分比第一次出現(xiàn)大于或等于80%時(shí)停止百分比累計(jì)，即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ù)按加工時(shí)間 Pi進(jìn)行不減排列，即 An-1≥An，n=1，2，…n；

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

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

（5）取剩余任務(wù)中加工時(shí)間最長(zhǎng)任務(wù)（未加工任務(wù)中加工時(shí)間最長(zhǎng)者）排在Fm最小機(jī)臺(tái)上；

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

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

表2 符號(hào)定義表Tab.2 Symbol Definition Table

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

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

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

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

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

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

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

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

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

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

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

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

（2）存在一個(gè)n使

（3）任務(wù)Jj提前投入生產(chǎn)時(shí)間記為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ī)臺(tái)Mm上加工任務(wù)提前生產(chǎn)時(shí)間總和記為Em，Em最小機(jī)臺(tái)Mm即為任務(wù)Jj加工機(jī)臺(tái)，機(jī)臺(tái)Mm上加工任務(wù)Ja最終開(kāi)始加工時(shí)間

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

4 仿真案例實(shí)踐

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

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

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

5 結(jié)束語(yǔ)

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