[發(fā)明專利]初始工件帶有釋放時間的返工工件重調度的分段插入算法

有效

• 申請?zhí)枺?/td>: 201310026667.4
• 申請日: 2013-01-19
• 公開（公告）號: CN103123486A
• 公開（公告）日: 2013-05-29
• 發(fā)明（設計）人: 郭艷東;倫淑嫻;楊凱;王巍;蘇憲利;周建壯;韓志艷
• 申請（專利權）人: 渤海大學
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 錦州遼西專利事務所 21225
• 代理人: 李輝

技術領域

本發(fā)明涉及工業(yè)工程領域中離散制造系統(tǒng)的返工工件的加工管理技術，是一種修正式的重調度方法。具體地，針對例如半導體、石英玻璃等一種生產中已知初始工件帶有釋放時間,優(yōu)化目標任意的初始調度,重調度的目標是在滿足初始工件具有最長等待時間約束下,最小化所有工件的最長等待時間問題(rescheduling?rework?jobs?on?a?single-machine),?簡稱為RRJS的方法，即提出了一種分段插入啟發(fā)式（Segment?Insert?Heuristic）算法，簡稱為SIH算法：這種算法在滿足約束的前提下以充分利用設備的空閑時間，將返工工件更多的插入初始調度為思想，以提升重調度決策的有效性、生產線的高效性和制造系統(tǒng)的穩(wěn)定性。

背景技術

調度問題一直以來是理論研究和生產實踐的熱點，工件排序也是比較經典和復雜的問題。在生產實踐中，通常在生產前計劃好工件的調度順序，稱為初始調度。所謂重調度就是指在已經制定好的初始調度執(zhí)行前，由于實際出現例如：新工作到來、機器故障、人員變更、緊急工作到來、返工工作、原材料不能按時到達等各種復雜情況，初始的調度不能適應實際狀況，在條件允許的情況下對初始調度進行調整，從而獲得當前的最優(yōu)調度。

重調度問題已經引起國內外研究者和實踐者的重視。包括：處理新任務的到來的重調度,預加工工件不可用的重調度,機器中斷的重調度，針對具體實際問題的重調度,多目標的加工車間重調度,流水車間環(huán)境下的重調度,任務隨時間惡化的重調度等；問題方法包括：動態(tài)規(guī)劃、魯棒優(yōu)化、分支定界、啟發(fā)式算法、智能算法等等。

在Operation?Research（運籌學）期刊上發(fā)表的Rescheduling?for?New?Orders（新到工件的重調度）一文在工件重調度領域的方法比較有代表性,他們研究了幾種單機重調度問題,?提出了幾種最優(yōu)算法。但是所提出的方法僅適用于解決約束為：初始工件的最大延遲數、延遲數和、最長延遲時間、延遲時間和受限于某一定值,目標函數為最小化完工時間和最小化最大完工時間工件重調度的問題。之后的很多研究者和實踐者沿著這個思路進行了重調度的研究。但是現有技術方法沒有考慮到以下情況：（1）初始工件帶有不同的到達時間，初始調度存在機器空閑時間。（2）重調度目標和初始調度目標不同。（3）初始工件受到等待時間的約束。

在實際生產中即使初始調度針對某一目標函數是最優(yōu)的調度,由于需要對返工工件進行處理,從而打擾了初始調度,根據實際需要可能要調整目標函數,因此初始調度對于重調度的目標來講就不一定是最優(yōu)的調度了。另外,初始工件到達通常具有不同時間,因此初始調度大多帶有機器空閑時間。同時,在離散制造業(yè)中,很多工位上根據工件制造工藝的要求,在工件到達后必須在一個時間窗口內進行操作加工,即受到等待時間的約束。在各種約束條件下，RRJS問題屬于典型的組合優(yōu)化問題，RRJS問題為多項式時間不可解（即NP難）問題，即如何確定最佳的重調度方案是一項困難的工作。因此針對上述普遍存在的實際問題亟待發(fā)明一套行之有效的解決方法。

發(fā)明內容

本發(fā)明針對已知一任意優(yōu)化目標????????????????????????????????????????????????的初始調度，包含一組數量為??的初始工件?,每個工件具有不同的釋放時間為?,，當最初的工件已經調度完畢，但未開始處理之前有一組數量為??的需返工工件?到來，需要返工的工件到達時間、裝設均為0；不失一般性，如果已經有一部分工件已經處理，則把剩余未處理的工件看成是最初的工件。在滿足初始工件最長等待時間限值為?的條件下,根據返工工件情況進行重新調度,從而獲得目標為所有工件最小化最大等待時間的重調度?問題。

本發(fā)明涉及的初始工件帶有釋放時間的返工工件重調度的分段插入算法，具體步驟如下：

第1步：將返工工件按照處理時間的非降序排列，得到調度?，表示第?個位置的工件號，計算第?個位置之前的處理時間和，；

第2步：按下列步驟執(zhí)行：

第2.1步：如果?,并且?，執(zhí)行第2.1.1步；如果?,,則?；如果?；

第2.1.1步：如果且,則計算，；選擇，執(zhí)行第2.2步，否則?；如果執(zhí)行第2.1步，如果?則?執(zhí)行第2.2步；

第2.2步：如果，在之前插入，否則?；更新中工件的所有開始時間,使?的開始時間等于?,；如果?；否則；?,=，，返回到第2.1步；