單機(jī)可拒絕分批排序中的若干問(wèn)題.pdf

1、分批排序是興起于20世紀(jì)90年代初應(yīng)用背景極強(qiáng)的一類(lèi)組合最優(yōu)化問(wèn)題，它主要產(chǎn)生于大規(guī)模的現(xiàn)代化生產(chǎn)流水作業(yè)線(xiàn)。工件加工可拒絕的排序問(wèn)題是近年來(lái)出現(xiàn)的一類(lèi)新型排序問(wèn)題，該問(wèn)題更符合實(shí)際情況，具有重要的現(xiàn)實(shí)意義。本文將分批排序與可拒絕排序相結(jié)合，討論了一些可拒絕分批排序問(wèn)題，論文主要結(jié)構(gòu)安排如下：
　　第一章是本文的緒論部分，主要介紹了排序問(wèn)題的背景、相關(guān)概念以及所需的基本知識(shí)，然后介紹了本文的主要結(jié)果和創(chuàng)新點(diǎn)。
　　第二章中首

2、次研究了目標(biāo)函數(shù)為極小化總加權(quán)完工時(shí)間加上被拒絕工件的拒絕費(fèi)用之和的單機(jī)可拒絕分批排序問(wèn)題。證明了該問(wèn)題是NP-難的，然后給出了基于動(dòng)態(tài)規(guī)劃的偽多項(xiàng)式時(shí)間算法和FPTAS。
　　第三章中首次研究了兩類(lèi)特殊情況下的可拒絕分批排序問(wèn)題。一個(gè)是極小化加權(quán)總完工時(shí)的有界批量可拒絕分批排序問(wèn)題，考慮了該問(wèn)題的一些特殊情況，如所有工件加工時(shí)間都相等、工件有兩種到達(dá)時(shí)間；另一個(gè)是極小化最大延遲的無(wú)界批量可拒絕分批排序問(wèn)題，考慮了所有工件的拒絕費(fèi)