基于動(dòng)態(tài)優(yōu)先級(jí)的離散車(chē)間調(diào)度系統(tǒng)開(kāi)發(fā)

□呂偉

上海電氣集團(tuán)股份有限公司 中央研究院　上海　200070

基于動(dòng)態(tài)優(yōu)先級(jí)的離散車(chē)間調(diào)度系統(tǒng)開(kāi)發(fā)

□呂偉

上海電氣集團(tuán)股份有限公司 中央研究院上海200070

通過(guò)分析某離散車(chē)間加工情況和調(diào)度人員經(jīng)驗(yàn)，為不同加工工序定義不同類(lèi)別的優(yōu)先級(jí)，建立動(dòng)態(tài)優(yōu)先級(jí)模型。在此基礎(chǔ)上，開(kāi)發(fā)了一套離散車(chē)間調(diào)度系統(tǒng)，建立了動(dòng)態(tài)調(diào)用優(yōu)先級(jí)模型，在考慮資源約束的情況下，生成了有效的排程方案。

隨著市場(chǎng)競(jìng)爭(zhēng)加劇，原材料價(jià)格與人力成本不斷提高，制造業(yè)面臨著提高生產(chǎn)效益、降低生產(chǎn)成本以應(yīng)對(duì)行業(yè)競(jìng)爭(zhēng)的挑戰(zhàn)。在現(xiàn)代制造企業(yè)中，面對(duì)不同的客戶(hù)需求進(jìn)行定制化生產(chǎn)，這對(duì)生產(chǎn)加工的靈活性要求很高。車(chē)間調(diào)度在生產(chǎn)計(jì)劃的實(shí)施中占據(jù)關(guān)鍵地位，良好的車(chē)間調(diào)度可以使資源得到優(yōu)化配置，能大大提高企業(yè)的經(jīng)濟(jì)效益。

離散型制造企業(yè)的生產(chǎn)過(guò)程復(fù)雜，生產(chǎn)計(jì)劃制定困難。產(chǎn)品加工過(guò)程中，不同的產(chǎn)品會(huì)經(jīng)過(guò)不同的加工車(chē)間，同一加工車(chē)間內(nèi)對(duì)不同設(shè)備的需求也不同，這些差異經(jīng)常導(dǎo)致工作流的不平衡。離散型車(chē)間的產(chǎn)品加工周期一般較長(zhǎng)，工作流的不平衡致使有些加工任務(wù)在工作中心的排隊(duì)時(shí)間較長(zhǎng)，導(dǎo)致加工時(shí)間的延遲和在制品的堆積。傳統(tǒng)的生產(chǎn)組織方式無(wú)法對(duì)資源進(jìn)行動(dòng)態(tài)調(diào)整，很難滿(mǎn)足客戶(hù)需求。

調(diào)度能夠有效地解決業(yè)務(wù)競(jìng)爭(zhēng)導(dǎo)致的工作流不平衡，是解決資源共享的有效手段［1］。關(guān)于動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，美國(guó)宇航局研究員C.L.Liu和J.W. Layland［2］最早提出了用于固定優(yōu)先級(jí)任務(wù)調(diào)度的速率單調(diào)任務(wù)調(diào)度算法。J.Y.T Leung和J.Whitehead等［3，4］提出了最小空閑時(shí)間優(yōu)先（Least Slack Time First，LSF）算法，該算法把作業(yè)剩余空閑時(shí)間作為優(yōu)先級(jí)評(píng)判標(biāo)準(zhǔn)，保證最緊迫的任務(wù)優(yōu)先執(zhí)行，主要應(yīng)用于分布式網(wǎng)絡(luò)、多媒體等領(lǐng)域。最早截止期優(yōu)先算法也是一種動(dòng)態(tài)優(yōu)先級(jí)任務(wù)調(diào)度算法，該算法根據(jù)任務(wù)截止期來(lái)決定任務(wù)執(zhí)行順序，其應(yīng)用范圍包括工業(yè)網(wǎng)絡(luò)、多媒體傳輸、軍事裝備等眾多領(lǐng)域［5］。

筆者研究的對(duì)象是某離散加工車(chē)間，主要生產(chǎn)方式是按訂單生產(chǎn)，研究目的是針對(duì)生產(chǎn)現(xiàn)場(chǎng)存在的諸多問(wèn)題，按照原材料的到料狀況、機(jī)械設(shè)備的使用狀況、生產(chǎn)能力等因素進(jìn)行綜合考慮，制定出合理的生產(chǎn)排程計(jì)劃，使原材料到位后生產(chǎn)能力及生產(chǎn)周期能滿(mǎn)足客戶(hù)的出貨需求，同時(shí)保證機(jī)器設(shè)備不沖突，人員工作時(shí)間安排均衡飽滿(mǎn)。

1　動(dòng)態(tài)優(yōu)先級(jí)模型

1.1模型假設(shè)

該離散車(chē)間是一個(gè)由50臺(tái)加工系統(tǒng)組成的機(jī)加工車(chē)間，每臺(tái)設(shè)備有對(duì)應(yīng)的操作人員，加工對(duì)象由14個(gè)零部件組成，零部件具有一定的裝配關(guān)系和加工順序約束，每個(gè)零部件包含若干道工序，且流程固定，50臺(tái)加工系統(tǒng)中包含車(chē)床組、銑床組、刨床組、鉗床組、磨床組、焊接組，各組設(shè)備的加工能力一致。車(chē)間調(diào)度員通過(guò)最佳的調(diào)度，為各工序選配最佳資源，在滿(mǎn)足設(shè)備加工能力及人員匹配的情況下，獲得最佳的排程方案。

動(dòng)態(tài)優(yōu)先級(jí)模型假設(shè)：①任何設(shè)備無(wú)法同時(shí)加工超過(guò)兩個(gè)工序；②任意工件無(wú)法同時(shí)在多臺(tái)設(shè)備上加工；③工件必須嚴(yán)格按照工藝路線(xiàn)在指定機(jī)器上加工；④除特定工序指定工人外，忽略工人的熟練程度；⑤工件的安裝及拆卸時(shí)間已經(jīng)包含在該工序的加工工時(shí)中；⑥一般情況下，有設(shè)備就有工人，除特殊情況外，工人處于充足狀態(tài)；⑦每個(gè)訂單的14種原材料到位時(shí)間隨機(jī)，遵循板材、管材、棒材的到位順序。

1.2優(yōu)先級(jí)指標(biāo)定義

在調(diào)度問(wèn)題中，最重要的是遇到多個(gè)任務(wù)可以同時(shí)在相同的設(shè)備上加工時(shí)，如何判定哪個(gè)任務(wù)先安排生產(chǎn)。本模型就是結(jié)合現(xiàn)場(chǎng)排程人員的歷史經(jīng)驗(yàn)，為現(xiàn)有加工過(guò)程定義不同類(lèi)別的優(yōu)先級(jí)，在生產(chǎn)過(guò)程中，動(dòng)態(tài)計(jì)算待加工工序的優(yōu)先級(jí)指標(biāo)，按優(yōu)先級(jí)順序組織生產(chǎn)。

該模型的研究重點(diǎn)就是根據(jù)排程人員的經(jīng)驗(yàn)，提出具體的規(guī)則，進(jìn)而定義不同類(lèi)別的優(yōu)先級(jí)。通過(guò)現(xiàn)場(chǎng)實(shí)地調(diào)研，本類(lèi)問(wèn)題在實(shí)際排程中可分為以下五種層次。

（1）項(xiàng)目?jī)?yōu)先級(jí)X。項(xiàng)目?jī)?yōu)先級(jí)預(yù)設(shè)值為a1，將不同項(xiàng)目按照重要性排序，由此分配項(xiàng)目重要性因子α（重要性越高，α越大），X=α×a1。

（2）零件優(yōu)先級(jí)Y。零件優(yōu)先級(jí)預(yù)設(shè)值為a2，根據(jù)零件裝配關(guān)系和加工順序的約束，結(jié)合排程人員歷史經(jīng)驗(yàn)，將14個(gè)零件按重要性排序，由此分配零件重要性因子β（重要性越高，β越大），Y=β×a2。

（3）工序銜接優(yōu)先級(jí)Z。工序銜接優(yōu)先級(jí)預(yù)設(shè)值為a3，如某工序需要在某設(shè)備C上進(jìn)行加工，C的上一個(gè)任務(wù)為相同零件的相同工序，那么該工序在該設(shè)備上的工序銜接優(yōu)先級(jí)為Z=a3。

（4）工序優(yōu)先級(jí)M。工序優(yōu)先級(jí)的基礎(chǔ)值設(shè)置為a4，如零件i共有k道工序，那么零件i的j道工序的工序優(yōu)先級(jí)為M=（j/k）×a4。

（5）時(shí)長(zhǎng)優(yōu)先級(jí)N。時(shí)長(zhǎng)優(yōu)先級(jí)的基礎(chǔ)值設(shè)置為a5，如某零件某工序需要加工時(shí)間m（單位為min），一套組件由n個(gè)零件組成，（m×n）max為所有零件工序中總加工時(shí)長(zhǎng)的最大值，那么該道工序的時(shí)長(zhǎng)優(yōu)先級(jí)為

1.3模型建立

根據(jù)定義的優(yōu)先級(jí)指標(biāo)，系統(tǒng)在進(jìn)行調(diào)度安排時(shí)會(huì)動(dòng)態(tài)計(jì)算待加工工序的優(yōu)先級(jí)，按照優(yōu)先級(jí)排序，將各工序依照BOM表安排到當(dāng)前空閑的加工設(shè)備上。在計(jì)算優(yōu)先級(jí)時(shí)，根據(jù)不同情況優(yōu)先級(jí)的比較規(guī)律，系統(tǒng)形成了比較通用的優(yōu)先級(jí)比較方法，主要在三個(gè)層面進(jìn)行比較：

根據(jù)以上定義，結(jié)合排程員的經(jīng)驗(yàn)，得到如圖1所示判定任務(wù)選擇的動(dòng)態(tài)優(yōu)先級(jí)模型。

2　調(diào)度系統(tǒng)軟件設(shè)計(jì)

2.1業(yè)務(wù)流程分析

車(chē)間現(xiàn)場(chǎng)調(diào)度的情況非常復(fù)雜，現(xiàn)場(chǎng)的排程條件是隨時(shí)變化的，系統(tǒng)需要綜合考慮項(xiàng)目安排、工藝、人員、設(shè)備、原材料等基礎(chǔ)資源的可用情況，還要對(duì)設(shè)備宕機(jī)、新原材料到達(dá)、插單等特殊工況給出快速反應(yīng)，生成合理的排程方案，圖2給出了生產(chǎn)調(diào)度的主要流程，車(chē)間的作業(yè)流程劃分為：現(xiàn)場(chǎng)加工、排程計(jì)劃、監(jiān)控三個(gè)部分，整個(gè)車(chē)間的作業(yè)以排程方案來(lái)驅(qū)動(dòng)，通過(guò)調(diào)用動(dòng)態(tài)優(yōu)先級(jí)算法模型，制定可執(zhí)行的、高效的排程方案。

為了有效執(zhí)行計(jì)劃，不能將排程計(jì)劃直接下達(dá)，而需要依賴(lài)派工單將命令傳達(dá)到各生產(chǎn)工位。根據(jù)動(dòng)態(tài)優(yōu)先級(jí)算法模型得出的排程方案，按零件劃分生成派工單，下達(dá)零件加工的設(shè)備、人員、時(shí)間安排，派工單隨零件在各工位流轉(zhuǎn)，在指導(dǎo)生產(chǎn)過(guò)程的同時(shí)，也可以實(shí)現(xiàn)對(duì)生產(chǎn)過(guò)程的監(jiān)控，反饋計(jì)劃的執(zhí)行情況，為下一期生產(chǎn)計(jì)劃的編制提供參考。

圖1　動(dòng)態(tài)優(yōu)先級(jí)模型

圖2　生產(chǎn)調(diào)度主要流程

2.2調(diào)度系統(tǒng)模塊劃分

根據(jù)生產(chǎn)調(diào)度的工作流程可知，調(diào)度系統(tǒng)軟件需實(shí)現(xiàn)的功能為：根據(jù)基礎(chǔ)信息的設(shè)定，調(diào)用動(dòng)態(tài)優(yōu)先級(jí)模型，生成排產(chǎn)計(jì)劃，根據(jù)排產(chǎn)計(jì)劃得到派工單，用于車(chē)間指導(dǎo)生產(chǎn)，收集計(jì)劃執(zhí)行的數(shù)據(jù)，用于管理者了解生產(chǎn)計(jì)劃的執(zhí)行情況，以及設(shè)備的運(yùn)行狀況。同時(shí)為確保安全性，系統(tǒng)對(duì)用戶(hù)的賬戶(hù)和權(quán)限要統(tǒng)一管理。根據(jù)以上分析，建立調(diào)度系統(tǒng)軟件的4個(gè)功能模塊：系統(tǒng)用戶(hù)管理、基礎(chǔ)信息維護(hù)、生產(chǎn)排程管理、信息查詢(xún)模塊，具體功能如圖3所示。

整個(gè)調(diào)度系統(tǒng)的核心部分是動(dòng)態(tài)優(yōu)先級(jí)模型，模型的實(shí)現(xiàn)依賴(lài)于生產(chǎn)排程管理模塊的功能。生產(chǎn)排程管理模塊可以根據(jù)現(xiàn)場(chǎng)原材料到位情況和機(jī)器、人員、設(shè)備的可用情況，調(diào)用動(dòng)態(tài)優(yōu)先級(jí)模型，動(dòng)態(tài)地計(jì)算待加工工序的優(yōu)先級(jí)，按照優(yōu)先級(jí)排序，對(duì)各工序安排機(jī)器和人員執(zhí)行加工任務(wù)，將結(jié)果以甘特圖（甘特圖：基于作業(yè)排序的目的，以圖示的方式通過(guò)活動(dòng)列表和時(shí)間刻度形象地表示出任何特定項(xiàng)目的活動(dòng)順序與持續(xù)時(shí)間）的形式顯示到界面中，并根據(jù)結(jié)果生成派工單，以便于將生產(chǎn)命令下達(dá)到各個(gè)工位上。

2.3與相關(guān)系統(tǒng)的信息交互

調(diào)度系統(tǒng)通過(guò)建立一套計(jì)算機(jī)軟件系統(tǒng)，通過(guò)一些固化的排程規(guī)則，平衡有限生產(chǎn)能力和物料需求，最大限度消除或減少人為因素對(duì)生產(chǎn)的干預(yù)，幫助離散制造企業(yè)建立精準(zhǔn)、詳盡的生產(chǎn)計(jì)劃。作為一套排程工具，生成的排程方案需要依靠現(xiàn)場(chǎng)的MES系統(tǒng)執(zhí)行，生成排程方案的基礎(chǔ)信息來(lái)自于ERP系統(tǒng)，系統(tǒng)之間存在密切的交互，如圖4所示。ERP向調(diào)度系統(tǒng)下發(fā)訂單信息、原料信息、生產(chǎn)配料信息、設(shè)備信息和標(biāo)準(zhǔn)工藝路線(xiàn)。調(diào)度系統(tǒng)根據(jù)下發(fā)的信息，制定排程方案，生成派工單下達(dá)至MES系統(tǒng)執(zhí)行。同時(shí)，MES系統(tǒng)采集到的加工進(jìn)度和設(shè)備狀態(tài)數(shù)據(jù)會(huì)實(shí)時(shí)反饋到調(diào)度系統(tǒng)，用于生成下一時(shí)刻的排程方案。

圖3　系統(tǒng)軟件模塊劃分

圖4　系統(tǒng)信息交互

3　系統(tǒng)實(shí)現(xiàn)

調(diào)度系統(tǒng)選用的客戶(hù)端操作系統(tǒng)為Windows 7，服務(wù)器端操作系統(tǒng)為Windows Server 2008，數(shù)據(jù)庫(kù)軟件為 SQL Server 2008，系統(tǒng)開(kāi)發(fā)工具為VB.NET。動(dòng)態(tài)優(yōu)先級(jí)算法部分由MATLAB2011編寫(xiě)，打包生成.dll文件由VB程序直接調(diào)用。

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

本課題通過(guò)對(duì)某離散加工車(chē)間的實(shí)地調(diào)研，從企業(yè)需求分析入手，開(kāi)發(fā)了針對(duì)按訂單生產(chǎn)、多品種小批量的離散型制造條件下的生產(chǎn)調(diào)度系統(tǒng)。通過(guò)分析現(xiàn)場(chǎng)存在的諸多約束條件和排程人員的經(jīng)驗(yàn)，形成動(dòng)態(tài)優(yōu)先級(jí)模型，利用該模型充分調(diào)用資源，找到最佳排程方案，大大提高了生產(chǎn)車(chē)間的效率和穩(wěn)定性。

［1］張登銀，許揚(yáng)揚(yáng)，蔣娟.基于時(shí)延的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（2）：162-165.

［2］LIUCL，LAYLANDJW.SchedulingAlgorithmsforMultiprog ramming in a Hard-Real-Time Environment［J］.Journal of the Association for Computing Machinery，1973，20（1）：46-61.

［3］LEUNGJ YT，WHITEHEADJ.On the ComplexityofFixedprioritySchedulingofPeriodicReal-timeTasks［J］. Performance Evaluation，1982，2（4）：237-250.

［4］夏家莉，陳輝，楊兵.一種動(dòng)態(tài)優(yōu)先級(jí)實(shí)時(shí)任務(wù)調(diào)度算法［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35（12）：2685-2695.

［5］NARLIKAR G，WILFONG G，ZHANG L.Designing Multihop Wireless Backhaul Networks with Delay Guarantees［J］. Wireless Networks，2010，16（1）：237-254.

By analyzing the case of a discrete processing workshop and the experience of dispatchers，varied levels of priorities are defined against different working operations for establishment of dynamic priority model. On this basis，we developed a set of discrete workshop scheduling system that can enable dynamic calling of the priority model togenerate an efficient scheduling scheme in consideration of resource constraints.

動(dòng)態(tài)優(yōu)先級(jí)模型；排程方案；調(diào)度系統(tǒng)

Dynamic Priority Model；Scheduling Scheme；Scheduling System

TP 311.1

B

1672-0555（2016）01-033-04

2015年9月

呂偉（1989—），女，碩士，研發(fā)工程師，主要研究方向：智能制造系統(tǒng)