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

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

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