同類雙目標(biāo)排序問題研究.pdf

1、排序問題是一類非常重要的組合最優(yōu)化問題，排序是在一定的約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配和安排次序。在經(jīng)典的排序問題中，大多數(shù)情況都是研究?jī)H一個(gè)目標(biāo)函數(shù)的單目標(biāo)排序問題。然而在生產(chǎn)管理實(shí)踐中有些情況不僅僅只需要考慮一個(gè)方面的性能指標(biāo)，而是需要綜合考慮多個(gè)性能指標(biāo)，即需要求解多個(gè)目標(biāo)函數(shù)的最優(yōu)或近似最優(yōu)或在某目標(biāo)函數(shù)約束范圍下求其它一些函數(shù)的最優(yōu)或近似最優(yōu)解的排序。多目標(biāo)排序問題被廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)、生產(chǎn)管理等其它各個(gè)領(lǐng)域，具有廣泛的

2、生產(chǎn)實(shí)踐背景和應(yīng)用價(jià)值。
　　 本論文共分為五個(gè)章節(jié):
　　 第一章簡(jiǎn)述排序問題的基本理論。
　　 第二章介紹本文主要研究的兩類多目標(biāo)排序問題的研究成果和發(fā)展現(xiàn)狀。
　　 第三章研究以工件總誤工數(shù)為第一目標(biāo)，以最小加權(quán)總提前完工時(shí)間為第二目標(biāo)的雙目標(biāo)函數(shù)排序問題。對(duì)該排序問題，在文獻(xiàn)[1]的基礎(chǔ)上提出分支定界算法，并給出幾種特殊情況下的多項(xiàng)式算法；進(jìn)一步，將單機(jī)排序中的所得結(jié)論推廣到m臺(tái)平行機(jī)的排序中，得