若干單機在線排序問題研究.pdf

1、該文選擇單機排序問題為研究對象,并且研究單機排序問題的動態(tài)在線情況.首先建立了一般化中斷模型,然后在此基礎上研究了幾類單機排序問題的動態(tài)在線最優(yōu)排序問題.該文所做的工作如下:首先,我們一般化了任務中斷模型.討論了定義在更一般意義下的可中斷動態(tài)單機排序問題,即任務被中斷后不能簡單的恢復加工,而是需要有一定的時間延遲,延遲是由任務的安裝時間和任務在中斷后恢復加工時其一部分(或全部)需要返工的時間兩部分共同造成的情況.通過刻化上述條件,給出了

2、兩種中斷—安裝重復模型一般化了任務可中斷的概念.其次,我們研究了總加權最小完工時間的在線調度問題.用建立起來的兩個中斷—安裝重復模型來研究具有任意的和未知的任務到達時間的最小化總加權完工時間問題,和最小化時間表長這兩類單機動態(tài)排序問題,給出了只考慮當前可用信息的在線調度規(guī)則.第三,我們研究了排序問題的動態(tài)在線調度問題.考慮該問題在中斷—重復和中斷—安裝重復模型下的動態(tài)在線排序問題,給出了只考慮當前可用信息的在線調度規(guī)則.第四,我們研究了