工件具有子工件工期的排序問題
關(guān)鍵詞：排序 子工件工期 啟發(fā)式算法
摘要：研究了工件具有子工件工期的排序問題.需要在一臺(tái)單機(jī)上加工若干個(gè)給定的工件.每個(gè)工件由若干個(gè)子工件組成,每個(gè)子工件都有各自的工期.只有當(dāng)工件的每個(gè)子工件都按時(shí)完成,才能稱該工件是按時(shí)完工工件,否則,稱該工件產(chǎn)生延誤.目標(biāo)是最大化按時(shí)完工的工件個(gè)數(shù).證明當(dāng)每個(gè)工件都被分成兩個(gè)子工件時(shí),該問題是NP-難的,而且不存在完全多項(xiàng)式時(shí)間近似方案(fully polynomial time approximation scheme,簡(jiǎn)記為FPTAS).提出兩個(gè)啟發(fā)式算法,利用數(shù)值模擬比較它們的性能,并且將這兩個(gè)啟發(fā)式算法的解與最優(yōu)解的上界進(jìn)行比較.
運(yùn)籌學(xué)學(xué)報(bào)雜志要求:
{1}屬于基金資助項(xiàng)目或立項(xiàng)課題的來(lái)稿，請(qǐng)注明項(xiàng)目或課題名稱、編號(hào)，多項(xiàng)基金項(xiàng)目應(yīng)依次列出。
{2}本刊實(shí)行以同行審稿為基礎(chǔ)的三審制（編輯初審、專家外審、編委會(huì)終審）。審稿過(guò)程中保護(hù)作者稿件的私密權(quán)。對(duì)不擬刊用的稿件將告知退稿意見，對(duì)稿件處理有不同意見者，作者有權(quán)申請(qǐng)復(fù)議，并提出申訴的文字說(shuō)明。
{3}參考文獻(xiàn)采用順序編碼制，按文獻(xiàn)在文中出現(xiàn)的先后順序排列。以不少于10條為宜。直接引用須標(biāo)注具體頁(yè)碼，概述性引用可標(biāo)注頁(yè)碼范圍。
{4}摘要應(yīng)按“四要素"書寫，即：目的、方法、結(jié)果、結(jié)論；綜述文章可不按“四要素"書寫。中、英文摘要應(yīng)300字左右，英文摘要300個(gè)單詞左右。
{5}論文內(nèi)容要求：題目、作者姓名、單位、摘要、關(guān)鍵詞、圖題和表題、基金、第一作者簡(jiǎn)介。
注：因版權(quán)方要求，不能公開全文，如需全文，請(qǐng)咨詢雜志社
