排序问题在解决经济、管理、工程、军事以及社会等领域的问题中起着越来越重要的作用。本文研究的问题为:单机上排列n个工件，目标函数为极大化所有工件剩余价值之和。该问题来源于诸如以下几个方面的应用:电影放映排序、重新加工再利用高科技产品、互联网传输、网络广告等。　　在本文中我们主要研究以下两类工件。恶化工件即工件加工时间随着开工时间的延后而增大;价值恶化工件即工件价值岁着开工时间延后而增加。结合这两种工件的性质，我们提出了第一种特殊工件，该种工件的价值是关于完工时间的指数函数，加工时间是关于开工时间的一次函数，即pj=bj(a+bt)（bj，a，b＞0），t为工件的开工时间。本论文第二种特殊工件的加工时间恒定，其价值同样是关于完工时间的指数函数，即我们定义的价值退化工件。　　为了解决这两种特殊工件单机上的排序问题，我们引进了分支定界算法。该算法首先通过启发式算法产生一个初始解，并结合我们得到的上界搜索最优解，通过剪掉一定不会包含最优解的分支提高计算效率。最后，我们在计算机上做了一些数值实验以评测本文分支定界算法的效率。