1、排序問題是經(jīng)典組合優(yōu)化的問題，在線和半在線排序是排序論當(dāng)前研究的熱點(diǎn)問題之一。本文主要討論工件有到達(dá)時(shí)間的一些在線和半在線模型，并分析算法下的競爭比。全文共分為三章。
　　 第一章是緒論部分，主要是介紹組合優(yōu)化中排序問題，競爭比分析和近似算法等基本概念，總結(jié)近幾年來出現(xiàn)的在線和半在線模型及有關(guān)的結(jié)論。
　　 第二章考慮同型平行機(jī)器上工件到達(dá)時(shí)間任意且工件加工時(shí)間單調(diào)不增的問題，目標(biāo)函數(shù)為極小化最大機(jī)器負(fù)載的在線模型。根據(jù)

2、LS算法，證明LS算法的最壞性能比不大于2-1/2m，并且當(dāng)m=1時(shí)，這個(gè)界為緊界。
　　 第三章考慮工件到達(dá)時(shí)間不減，機(jī)器加工速度為si=1(1≤i≤m-1)，sm=s＞1的在線排序。目標(biāo)函數(shù)為極小化最大機(jī)器負(fù)載的在線模型，主要討論兩個(gè)問題：1，當(dāng)m=2時(shí)，當(dāng)其中1臺(tái)機(jī)器的加工速度為1而有一臺(tái)機(jī)器的加工速度為s＞1時(shí)，證明LS算法的最壞性能比不大于2；2，當(dāng)其中m-1臺(tái)機(jī)器的加工速度為1而有一臺(tái)機(jī)器的加工速度為s＞1時(shí)，證明L