最大化按時完工工件個數(shù)的單位長度工件的單機在線分批排序問題.pdf

1、授 予單位代碼 10 4 5 92 0 0 6 12 0 14 0 7 0 10 5 0 0 3 號 級 學(xué) 密文學(xué) 論 大 位 州 學(xué) 鄭 士碩(科 學(xué) 學(xué)位 )最 大 化 按 時完 工 工件個 數(shù) 的單位 長 度工 件 的一 單機 在 線 分批排 序 問題院 系 名 稱 : 數(shù) 學(xué) 系學(xué) 科 門 類 : 理 學(xué)專 業(yè) 名 稱 : 運 籌 學(xué) 與控 制 論作 者 姓 名 : 李文 杰 二導(dǎo) 師 姓 名 、職 稱 : 原晉 江 教授二

2、零 零 九 年 四 月摘 要本文研 究在 Looka h ead 作用下 的單位長度工件 的單機在線平行分批排序 向題 . 目標 函數(shù) 為求最大 按 時完 工工件個 數(shù) . 平行 分 批是 指 ，多個 工 件 可 以組成一 批 同 時 加 工 ，而 每 一 批 的加 工 時 間等 于該 批 中工 件 的最 長 加 工 時 間 。我 們 用‘ 二co 和 b < co 分 別表 示批容量 無 限制 和有 限制 . L 凡 模 型是指

3、 ，在 一時刻 點t ，在 線 算 法 可 以預(yù) 見在 時 間段 ( ， ， ， + 勸 內(nèi)將 要 到達 工件 的全 部 信 息 . 本 文 的主要結(jié) 果 如 下 .( 1 ) 當 0 三L < 1 時，我們證 明了一個簡 單 的貪婪 在 線算法 是最 好可能 的在線算法 . 該算 法 的競 爭 比為 l/m i n{。 ， b + 1} ，其 中 n 表示工件個 數(shù). 這 意 味Lo oka h ead 在這 種情 形 下是 沒