排序问题又称时间表理论,是组合优化的重要组成部分.它来源于我们实际的生产生活,并广泛应用于科学管理、航海运输、工程机技术等诸多领域.随着科技的进步和同行产业间竞争的加剧,对一个企业来说,如何安排生产和运输使得成本最优变得尤为重要.对客户来说,如何能够用相对较少的钱而得到最优的产品和服务也是我们作为消费者梦寐以求的.　　成比例退化工件的排序及供应链排序是比较现代的排序模型,本文对这几类问题进行了研究,做了如下工作.　　第1章介绍了排序问题的相关基本知识以及符号.　　第2章考虑两个带批配送的成比例退化工件的单机供应链排序问题.对于每一批配送的费用是和该批中工件的的个数有关,就极小化总完工时间加总配送费用问题,我们讨论了最优序的性质并设计分析了伪多项式时间最优算法.对于每一批配送的费用是固定常数情形,就极小化最大延迟和总配送费用问题,设计了算法并对算法的复杂性进行了分析.　　第3章研究成比例退化工件在有不可用时间段机器上的供应链排序问题,机器具有一个不可用区间,每一批配送的费用是固定常数.就极小化最大完工时间加总配送费用和总完工时间加总配送费用两个目标问题,首先分别分析证明了问题的NP-困难性,然后分别设计了问题的伪多项式时间动态规划算法,最后讨论了一种多项式可解的特殊情形.　　第4章考虑了带配送时间的成比例退化工件单机排序问题.对工件具有相同到达时间情形,我们证明了问题是多项式时间可解的.对工件具有不同到达时间情形,我们证明了问题是一般意义下NP-困难的,并且设计了一个多项式时间的2-近似算法.