調(diào)度系統(tǒng)中指派問題的符號算法研究.pdf

1、調(diào)度問題是一類NP完全問題,多年來一直吸引著無數(shù)研究人員的注意。調(diào)度問題的復(fù)雜性、調(diào)度領(lǐng)域知識的多樣性和生產(chǎn)環(huán)境的動態(tài)性決定了調(diào)度問題的解決必須融合多種技術(shù)的手段加以解決。本文將調(diào)度系統(tǒng)中的指派問題歸結(jié)為邏輯函數(shù)及其序列的操作和運算,利用符號技術(shù)來進(jìn)行求解。
　　論文的主要研究內(nèi)容包括:
　　第一,分析了有序二叉決策圖及其擴(kuò)展結(jié)構(gòu),并對其在符號技術(shù)中的應(yīng)用進(jìn)行了探討,為本文所提出的符號算法實驗仿真打下基礎(chǔ);
　　第二,

2、分析了調(diào)度系統(tǒng)中的指派問題特點及求解方法;針對實際生產(chǎn)中存在的并行加工現(xiàn)象,給出了加權(quán)指派問題的數(shù)學(xué)模型及其相應(yīng)的二部圖加權(quán)最優(yōu)半匹配算法,將二部圖加權(quán)半匹配問題轉(zhuǎn)化為經(jīng)典的二部圖權(quán)匹配問題進(jìn)行求解;
　　第三,比較分析了二部圖最優(yōu)半匹配符號算法與ASM1和ASM2的執(zhí)行效果,實驗結(jié)果表明,符號算法在處理高密度大規(guī)模圖時具有優(yōu)勢;
　　第四,基于 CUDD軟件包,給出了二部圖加權(quán)最優(yōu)半匹配符號算法,實驗結(jié)果表明,符號技術(shù)有效