最大化按時(shí)完工工件個(gè)數(shù)的單位長(zhǎng)度工件的單機(jī)在線分批排序問(wèn)題.pdf

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

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

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