The Complex Analysis and Algorithms for the Special Case of the Total Tardiness Problem on a Single Machine

摘要：

We consider NP-hard in the ordinary sense classical scheduling to-tal tardiness problem on a single machine. The special case of the problem when processing times of jobs are agreeable to due dates is studied and proved NP-hard in the ordinary sense too. Two pseudo-polynomial O(n2∑pj ), O(n∑pj) and two polynomial O(n2) algo-rithms are proposed to solve all subcases of this case. The even-odd partition problem is considered too. It is proved that the problem can be solved by our algorithm in no more than O(n∑pj) time.

关键词： scheduling single machine total tardiness even-odd partition hardness

作者: Alexander A.Lazarev

作者单位: Computing Centre of the Russian Academy of Sciences,Vavilov st.40,119991 Moscow GSP-1,Russia

会议类型: 国际会议

会议名称: 工业工程与系统管理2007年国际会议(International Conference on Industrial Engineering and Systems Management)(IESM 2007)

会议地点: 北京

会议语种:英文

在线出版日期: 2007-05-30（万方平台首次上网日期，不代表论文的发表时间）