帶有固定工件和工件運(yùn)輸時(shí)間的單機(jī)排序問(wèn)題.pdf

1、排序問(wèn)題有著深刻的實(shí)際背景和廣闊的應(yīng)用前景，一直受到國(guó)際學(xué)術(shù)界的重視．本文主要研究了帶有固定工件和工件運(yùn)輸時(shí)間的單機(jī)排序問(wèn)題。固定工件是一類(lèi)特殊的工件，它們的開(kāi)工時(shí)間和完工時(shí)間都是預(yù)先確定的，在時(shí)間軸上占據(jù)著一些互不相交的區(qū)間。在整個(gè)加工過(guò)程中，工件不允許中斷。每個(gè)工件有一個(gè)運(yùn)輸時(shí)間，我們假定在工件加工完后有足夠多的卡車(chē)運(yùn)輸。 論文共分兩章． 第一章(概述)主要介紹了排序的背景、發(fā)展、基本概念及排序模型的記法．

2、第二章主要討論了四個(gè)排序模型的復(fù)雜性、擬多項(xiàng)式時(shí)間算法和近似算法。用三參數(shù)法表示我們的模型即是： 1｜FB(F)，q<,j>｜L<,max>， 1｜FB(F)｜maxw<,j>C<,j>， 1｜FB，q<,j>｜L<,max>， 1｜FB(F)｜∑w<,j>C<,j>． 本文主要結(jié)果如下： (1)問(wèn)題1｜FB(F)，q<,j>｜L<,max>、 1｜FB(F)｜maxw<,j>C<,j>和1｜FB(F)｜∑w<,j>C<

3、,j>是NP-困難的，問(wèn)題1｜FB，q<,j>｜L<,max>是強(qiáng)NP-困難的。 (2)問(wèn)題1｜FB(F)，q<,j>｜L<,max>、1｜FB(F)｜maxw<,j>C<,j>和1｜FB(F)｜∑w<'j>C<,j>是擬多項(xiàng)式時(shí)間可解的。 (3)對(duì)于問(wèn)題1｜FB，q<,j>｜L<,max>給出了最壞性能比為2的近似算法，并證明這是最好可能的多項(xiàng)式時(shí)間近似算法； 對(duì)于問(wèn)題1｜FB(1)，q<,j>｜L<,max>