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