若干單機(jī)在線排序問題研究.pdf

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

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