帶有固定工件和工件運輸時間的單機排序問題.pdf

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

2、第二章主要討論了四個排序模型的復雜性、擬多項式時間算法和近似算法。用三參數(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>． 本文主要結果如下： (1)問題1｜FB(F)，q<,j>｜L<,max>、 1｜FB(F)｜maxw<,j>C<,j>和1｜FB(F)｜∑w<,j>C<

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