论文部分内容阅读
排序问题是一类重要的组合最优化问题。本文包括五个部分。第一章引言介绍排序问题的一些背景知识。第二章对工件加工时间与开工时间有关的恶化效应的情形，研究目标函数分别是最大完工时间和总完工时间的单机成组排序问题，并分别给出了问题1｜pij（α+bt），GT，Si｜Cmax和1｜pij（α+bt），GT，Si｜∑Cij的最优解。第三章讨论同时具有学习和恶化效应的单机排序问题：工件的加工时间是工件开工时间和工件加工位置的函数：Pj[r]=pjα（t）αr-1，并分别对目标函数是fi∈{Cmax，∑wjCj，∑Cδj，Lmax}的问题给出了多项式时间算法。第四章讨论工件加工时间具有学习和恶化效应并且安装时间具有恶化效应的单机排序问题，并给出了多项式时间算法；工件加工时间是（），安装时间是（），分别对目标函数是fi∈{Cmax，∑Cj，∑Cδj，Lmax，∑Tj）的排序问题给出了多项式时间算法。第五章综述了论文的结果以及提出一些今后研究工作的展望。