工件可自由下線(xiàn)最小化總完工時(shí)間的平行分批排序問(wèn)題
摘要：考慮工件可自由下線(xiàn)最小化總完工時(shí)間的有界平行分批排序問(wèn)題. 在該問(wèn)題中, 一臺平行批機器可以同時(shí)處理 b 個(gè)工件作為一個(gè)平行批, 這里b 是批容量, 一個(gè)批的加工時(shí)間等于分配給這個(gè)批的工件的最大加工時(shí)間. 關(guān)于可自由下線(xiàn)工件, 每一個(gè)工件的完工時(shí)間等于包含這個(gè)工件的批的開(kāi)工時(shí)間與工件的加工時(shí)間的和. 也就是, 如果一個(gè)批B 有一個(gè)開(kāi)工時(shí)間S, 那么包含在批B 中的每一個(gè)工件J_j 的開(kāi)工時(shí)間定義為S, 而它的完工時(shí)間定義為S＋p_j, 這里p_j 是工件J_j 的加工時(shí)間. 對此問(wèn)題, 首先研究最優(yōu)排序的一些性質(zhì). 然后, 基于這些性質(zhì), 給出一個(gè)運行時(shí)間為O（n^{b （b-1）}）的動(dòng)態(tài)規劃算法.
注: 保護知識產(chǎn)權,如需閱讀全文請聯(lián)系運籌學(xué)學(xué)報雜志社
相關(guān)推薦
更多學(xué)報.jpg)
于我們.jpeg)