【作者】 陈杰；

【导师】 刘朝晖；

【作者基本信息】 华东理工大学 ， 应用数学， 2011， 硕士

【摘要】 单机总延误问题1‖∑Tj是研究最为广泛的排序问题之一,由于总延误问题是NP-难的,所以经常采用拟多项式算法、分支定界算法和启发式算法。本文主要讨论一种新的启发式算法,对该算法的性质进行分析。该启发式算法每次安排一个工件,直到所有工件构成一个完整的序列,实际上是一种贪婪算法,主要基于下面的考虑：用合理交换的原则去识别延误最小的工件,并将该工件放在序列的最后一个位置,再考虑哪个工件位于前一个位置,依此类推。做出这样的选择,其目的在于使排在最后一个位置的工件所产生的延误最小,从而,在算法的后续阶段就会有更好的选择。我们不断的采用这样的思想,直到所有工件构建成一个完整的序列。更多还原

【Abstract】 The single machine total tardiness problem 1‖ΣTj is one of the most widely researched scheduling problems. As the total tardiness problem is NP-hard, pseudo-polynomial algorithms and approximation algorithms are often used.This paper presents a new heuristic algorithm and analyses the quality of algorithm. The proposed heuristic is basically a greed algorithm which sequences jobs one at a time until a complete sequence is constructed. We based our heuristic on the following observations. Pair wise interchange can be used to identify a most promising job for the last position in the job sequences. The choice is made to ensure that regardless of which job is sequenced second to last, the tardiness incurred by sequencing the last job is controlled to the smallest degree. This provides more opportunity in later stages of the algorithm. This idea is used recursively until the complete sequence is constructed.更多还原