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

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

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

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