關鍵詞：排序 子工件工期 啟發(fā)式算法 

摘要：研究了工件具有子工件工期的排序問題.需要在一臺單機上加工若干個給定的工件.每個工件由若干個子工件組成,每個子工件都有各自的工期.只有當工件的每個子工件都按時完成,才能稱該工件是按時完工工件,否則,稱該工件產(chǎn)生延誤.目標是最大化按時完工的工件個數(shù).證明當每個工件都被分成兩個子工件時,該問題是NP-難的,而且不存在完全多項式時間近似方案(fully polynomial time approximation scheme,簡記為FPTAS).提出兩個啟發(fā)式算法,利用數(shù)值模擬比較它們的性能,并且將這兩個啟發(fā)式算法的解與最優(yōu)解的上界進行比較.

運籌學學報雜志要求:

{1}屬于基金資助項目或立項課題的來稿，請注明項目或課題名稱、編號，多項基金項目應依次列出。

{2}本刊實行以同行審稿為基礎的三審制（編輯初審、專家外審、編委會終審）。審稿過程中保護作者稿件的私密權。對不擬刊用的稿件將告知退稿意見，對稿件處理有不同意見者，作者有權申請復議，并提出申訴的文字說明。

{3}參考文獻采用順序編碼制，按文獻在文中出現(xiàn)的先后順序排列。以不少于10條為宜。直接引用須標注具體頁碼，概述性引用可標注頁碼范圍。

{4}摘要應按“四要素"書寫，即：目的、方法、結果、結論；綜述文章可不按“四要素"書寫。中、英文摘要應300字左右，英文摘要300個單詞左右。

{5}論文內(nèi)容要求：題目、作者姓名、單位、摘要、關鍵詞、圖題和表題、基金、第一作者簡介。

注：因版權方要求，不能公開全文，如需全文，請咨詢雜志社