在现实生活中,经常会遇到一些工件的加工时间取决于开始加工时间的情况,工件开始进行加工的时间越晚,实际加工的时间就越长。同时,工人在重复执行相同或者相似的任务后,他们可以获取经验,生产效率会随着时间而不断提高。因此,工件的排序越靠后,加工的时间就会变得越短,这种现象被称为学习效应。另外,由于资源有限,决策者可能会选择部分工件来加工,这样就会对没有加工的工件产生一些惩罚,叫做拒绝惩罚。除此之外,通常由于机器维修或故障等原因,机器在一定时间内不能工作,这也就是机器的不可用区间。本文讨论带有拒绝的若干恒速机排序问题。具体内容概括如下:1.对于极小化接受工件的最大完工时间和拒绝工件的总惩罚之和的问题,进行了如下研究:（1）讨论了带有退化、学习效应和拒绝的m台恒速机排序问题。首先,对目标函数进行了修改,对于这个NP-难问题,每台机器上接受的工件按照最短基本加工时间优先顺序排列可以得到最优解,给出了一个全多项式近似策略（FPTAS）,并且分析了其时间复杂性为O（n3m+2L2m+2/ε2m+1）。（2）讨论了两台带有退化、拒绝和不可用区间的恒速机排序问题。在不可用区间前、后,及另一台机器上,工件按照{a,/b,}不减顺序进行排列可以得到最优解,给出了 FPTAS,时间复杂性为O（n6L4/ε3）。（3）讨论了两台带有拒绝和不可用区间的恒速机排序问题。首先,对目标函数进行了修改,给出最优解的性质,进而提出了一个FPTAS,其时间复杂性为O（n4L4/ε3）。2.对于极小化接受工件的总完工时间和拒绝工件的总惩罚之和的问题,讨论了带有退化、拒绝和不可用区间的两台恒速机的排序模型,其中的一台机器上带有一段不可用区间。对于这个NP-难的问题,依据最优解的性质,给出一个FPTAS,其时间复杂性为O（n9L6/ε5）。