若干車間作業(yè)排序問題的算法設(shè)計與分析.pdf

1、本文研究了自由作業(yè)和流水作業(yè)環(huán)境下的兩類排序問題模型，研究的核心是問題的近似算法設(shè)計和最壞情況界分析，全文共分五章，具體如下。
　　第一章簡要地介紹了排序問題的基本知識以及自由作業(yè)和流水作業(yè)的相關(guān)知識。
　　第二章研究了一類加工時間由工件和機器速度決定的三臺機自由作業(yè)排序問題，在此問題中工件首先要在三臺自由作業(yè)機器上加工，工件Jj在機器上的加工時間由工件長度pj和機器的速度si決定。目標(biāo)是極小化最大完工時間，用三參數(shù)表示為O

2、3|pij=pj/si|Cmax，我們設(shè)計了一個最壞情況界不大于5/4的近似算法。
　　第三章研究了一類工件加工不等待且機器具有多功能屬性的兩臺機流水作業(yè)排序問題，在此問題中工件首先要在兩臺流水作業(yè)機器上加工，工件Ji的兩個工序在加工過程中不能中斷，第一臺機可以加工工件Jj的兩個工序。目標(biāo)是極小化最大完工時間，用三參數(shù)表示為F2|nwt，mtflx|Cmax，我們改進了已有文獻的結(jié)果（最壞情況界為5/3），設(shè)計了一個最壞情況界不大

3、于13/8的近似算法。
　　第四章研究了一類工件加工不等待且可分割，機器具有多功能屬性的兩臺機流水作業(yè)排序問題，在此問題中工件首先要在兩臺流水作業(yè)機器上加工，工件的兩個工序在加工過程中不能中斷，第一臺機可以加工工件Jj的兩個工序，工件的第二個工序在加工過程中可以中斷。目標(biāo)是極小化最大完工時間，用三參數(shù)表示為F2|nwt，mtflx，prmp|Cmax，我們進一步推廣了現(xiàn)有的文獻結(jié)果（現(xiàn)有的文獻給出啟發(fā)式算法），設(shè)計了一個最壞情況界