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

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

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