排序论又称为时间表理论，其作为运筹学的一个分支，作为一门应用科学，有着深刻的实际背景和广阔的应用前景。分批排序、机器带准备时间的排序问题是近些年来新兴的排序模型，这两类模型更具有现实意义。本文将以上两种新的排序模型相结合，讨论机器有准备时间的分批排序问题，并在此基础下，考虑两个目标函数，极小化最大完工时间(Cmax)和加权总完工时间（∑wjCj），论文的结构如下安排：第一章，主要概述了排序问题的发展、研究现状，简单介绍了本文的主要研究成果。第二章，主要研究了机器带准备时间的平行机上的分批排序问题，这里目标函数为工件的极大完工时间，这类问题是NP-难的，已有的结果比较少。在本章我们结合FBLPT算法，Multifit算法和LPT算法，利用复制的方法分别对机器是同型机和同类机的两种情形设计出近似算法，并证明它们的最差性能比分别不超过（2-1／B）[9／7+（1／2）k]和5／3（2-1／B）。第三章，排序问题Pm，αi|B|∑wjCj是一个NP-难问题，本章主要考虑在工件的加工时间都相等的特殊情况下，即pj=p时，给出一个最优的算法，并且给出了最优性的证明。其次当工件的到达时间是常数个的情形，设计出一个最优算法，其时间复杂性为O(2mknlogn)，其中m为机器的台数、n为工件的个数、k为工件到达时间的个数。
本文来源: https://www.lw50.cn/article/34b1f62be3bbf01a1952861a.html