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