具有約束關(guān)系的三類單機(jī)排序問題的研究.pdf

1、排序問題研究的是若干個(gè)任務(wù)要在一些機(jī)器上進(jìn)行加工,如何安排機(jī)器和任務(wù)使得某些要求(目標(biāo)函數(shù))達(dá)到最優(yōu)的問題.按處理機(jī)個(gè)數(shù)將排序問題分為:單機(jī)排序問題和多處理機(jī)排序問題;根據(jù)任務(wù)加工時(shí)間和到達(dá)時(shí)間以及處理機(jī)的工作環(huán)境等數(shù)據(jù)是確定的或服從某種隨機(jī)分布可分為:確定性排序問題和隨機(jī)排序問題;根據(jù)所有任務(wù)的參數(shù)是否是預(yù)先給定的可分為:靜態(tài)排序問題和動(dòng)態(tài)排序問題.機(jī)器排序問題的研究到目前為止,已有很多很好成果,但仍存在大量的問題有待解決.該文在上述

2、研究的基礎(chǔ)上,研究了單機(jī)排序問題中的如下三類問題:1)證明了在考慮折扣因子的條件下,模塊M的p因子最大初始集合I<'*>中的任務(wù)優(yōu)先于模塊M中的其他任務(wù),并且被連續(xù)加工所得的排序?yàn)樽顑?yōu)排序;該結(jié)果推廣了Lawler用來求解約束為串并有向圖的單機(jī)加權(quán)總完工時(shí)間問題的由底向上搜索分解樹的方法.2)給出了一種新的啟發(fā)式算法;并將兩種啟發(fā)式算法的解作為遺傳算法初始群體中的個(gè)體,通過定義任務(wù)的兩個(gè)鄰域,給出求解此問題的雜交和變異算子,并用遺傳算法