一類訂單排序及兩類平行機(jī)排序問題.pdf

1、排序論作為最優(yōu)化理論的重要組成部分,在計(jì)算機(jī)系統(tǒng)、運(yùn)輸調(diào)度、生產(chǎn)管理等諸多領(lǐng)域有著廣泛的應(yīng)用,并且取得了大量有意義的成果。訂單排序問題是一類現(xiàn)實(shí)意義很強(qiáng)的排序問題,因而具有一定的研究?jī)r(jià)值。本文討論了這類問題的計(jì)算復(fù)雜性。近年來,伴隨著生產(chǎn)生活的需要而產(chǎn)生的工件具有優(yōu)先加工約束的排序問題和半在線(semi-online)模型越來越受到大家的重視。本文就三臺(tái)同型機(jī)上約束鏈的排序問題和兩臺(tái)帶準(zhǔn)備時(shí)間的同類機(jī)半在線問題進(jìn)行了研究。
　　論

2、文結(jié)構(gòu)安排如下:
　　第一章為緒論部分,首先介紹了排序問題的產(chǎn)生、意義及研究現(xiàn)狀,然后給出了必要的預(yù)備知識(shí),最后介紹了本文主要研究的問題及其結(jié)果。
　　第二章主要討論極小化帶多工類工件訂單的完工范圍問題:考慮同一類工件放在一起連續(xù)加工,任一工件的完工時(shí)間為其所在類中全部工件完工時(shí)的時(shí)間的情況,以訂單的完工時(shí)間范圍最小為優(yōu)化目標(biāo),證明了此問題為NP- hard,并給出了相應(yīng)的分枝定界算法。
　　第三章主要討論三臺(tái)同型機(jī)上