加工時(shí)間可控的分批排序問(wèn)題.pdf

1、分批排序問(wèn)題和加工時(shí)間可壓縮的排序問(wèn)題有著深刻的根源.在分批排序問(wèn)題中,機(jī)器一次最多可加工B個(gè)工件,工件在加工過(guò)程中不允許被打斷、移出或加入新工件；在加工時(shí)間可壓縮的排序問(wèn)題中,工件的加工時(shí)間參數(shù)是不固定的,因此我們可以壓縮工件原始的加工時(shí)間,產(chǎn)生壓縮費(fèi)用.本文將以上兩種現(xiàn)代排序模型結(jié)合起來(lái),討論了加工時(shí)間可控的分批排序問(wèn)題.論文共分為三章,主要結(jié)構(gòu)安排如下:
　　 第一章是緒論部分,簡(jiǎn)述了排序問(wèn)題的應(yīng)用背景及問(wèn)題描述,給出了必

2、要的預(yù)備知識(shí),并且介紹了本文的主要研究結(jié)論.
　　 第二章討論了工件具有動(dòng)態(tài)的到達(dá)時(shí)間時(shí)加工時(shí)間可控的分批排序問(wèn)題,目標(biāo)是使最大完工時(shí)間和加工時(shí)間可控所需費(fèi)用的總和最小.對(duì)工件具有常數(shù)個(gè)動(dòng)態(tài)的到達(dá)時(shí)間,設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法。其計(jì)算復(fù)雜性為O(mn(Bhphpsum)m-1).其中,m是工件的到達(dá)時(shí)間的個(gè)數(shù),n是工件的個(gè)數(shù),每一批最多含有B個(gè)工件。每個(gè)工件最多有h個(gè)可以選擇的加工時(shí)間,ph為工件的最大加工時(shí)間。psum為所有工件的最大