加工時(shí)間隨開工時(shí)間線性遞減的排序問題.pdf

1、排序問題是一類具有廣泛實(shí)際背景的組合最優(yōu)化問題，廣泛應(yīng)用于管理科學(xué)，計(jì)算機(jī)科學(xué)和工程技術(shù)等眾多領(lǐng)域。隨著現(xiàn)代工業(yè)的發(fā)展，經(jīng)典的排序模型不斷被突破。經(jīng)典排序中通常假設(shè)，工件的加工時(shí)間是固定不變的常量，而且工件只能在機(jī)器上順次逐個(gè)加工。然而在實(shí)際問題中，有的工件的加工時(shí)間隨其開工時(shí)間變化而變化，而且有些工件可以作為一批一起加工，因此對這類排序模型的研究具有重要的意義。本文主要研究工件加工時(shí)間隨開工時(shí)間線性變化的平行機(jī)排序問題及串行工件同時(shí)加

2、工排序問題。 首先介紹了排序問題的定義、分類及表示方法，以及工件加工時(shí)間依賴開工時(shí)間的排序問題和串行工件同時(shí)加工排序問題的研究現(xiàn)狀。然后分別對工件加工時(shí)間隨開工時(shí)間線性遞減的平行機(jī)排序問題和串行工件同時(shí)加工排序問題進(jìn)行了討論。第二章主要討論了兩個(gè)具有兩臺處理機(jī)的排序問題：一是平行機(jī)排序問題，另一個(gè)是每批恰為k個(gè)工件的串行工件同時(shí)加工排序的平行機(jī)排序問題。在這兩個(gè)問題中，工件加工時(shí)間均為開工時(shí)間的線性遞減函數(shù)，目標(biāo)函數(shù)均為極小化總

3、完工時(shí)間。對于第一個(gè)問題，證明了其最優(yōu)排序可由工件按基本加工時(shí)間不減排列得到，由此得出其最優(yōu)算法，并指出了該結(jié)論對于相應(yīng)的加工時(shí)間隨開工時(shí)間線性遞增的情況不成立。對于第二個(gè)問題，根據(jù)其與第一個(gè)問題在某些性質(zhì)上的相似性，給出了其最優(yōu)算法。最后指出本章所討論的兩個(gè)問題的結(jié)論均可推廣到m臺處理機(jī)的情況。第三章討論了一些工件加工時(shí)間隨開工時(shí)間線性遞減的串行工件同時(shí)加工排序問題。分別就單機(jī)和流水作業(yè)的情況給予了討論。對于單機(jī)排序問題，討論了目標(biāo)函