排序问题是一类具有广泛实际背景的组合最优化问题，广泛应用于管理科学，计算机科学和工程技术等众多领域。随着现代工业的发展，经典的排序模型不断被突破。经典排序中通常假设，工件的加工时间是固定不变的常量，而且工件只能在机器上顺次逐个加工。然而在实际问题中，有的工件的加工时间随其开工时间变化而变化，而且有些工件可以作为一批一起加工，因此对这类排序模型的研究具有重要的意义。本文主要研究工件加工时间随开工时间线性变化的平行机排序问题及串行工件同时加工排序问题。 首先介绍了排序问题的定义、分类及表示方法，以及工件加工时间依赖开工时间的排序问题和串行工件同时加工排序问题的研究现状。然后分别对工件加工时间随开工时间线性递减的平行机排序问题和串行工件同时加工排序问题进行了讨论。第二章主要讨论了两个具有两台处理机的排序问题：一是平行机排序问题，另一个是每批恰为k个工件的串行工件同时加工排序的平行机排序问题。在这两个问题中，工件加工时间均为开工时间的线性递减函数，目标函数均为极小化总完工时间。对于第一个问题，证明了其最优排序可由工件按基本加工时间不减排列得到，由此得出其最优算法，并指出了该结论对于相应的加工时间随开工时间线性递增的情况不成立。对于第二个问题，根据其与第一个问题在某些性质上的相似性，给出了其最优算法。最后指出本章所讨论的两个问题的结论均可推广到m台处理机的情况。第三章讨论了一些工件加工时间随开工时间线性递减的串行工件同时加工排序问题。分别就单机和流水作业的情况给予了讨论。对于单机排序问题，讨论了目标函数为极小化最大完工时间、总完工时间、最大延误等问题的最优排序的性质，同时就这些性质对相应的加工时间随开工时间线性递增的情况成立与否给予了讨论。对于流水作业排序问题，主要考虑了两种特殊情况。讨论了每批恰为k个工件、极小化最大完工时间问题的最优算法。论文最后对本文的内容作了总结，并提出了未来工作的努力方向。