同類雙目標排序問題研究.pdf

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

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