随着社会的发展，经典的组合优化问题在受到众多学者的关注的同时，又不断的产生了一些新的模型。本文就从逆目标函数的角度考虑了若干重要的组合优化问题，包括排序和装箱，我们将这类问题称为逆目标优化问题。事实上这类逆目标优化的问题文献中已有相关讨论，比如TSP--maximumTSP[9；25；40；48]；极小割——极大割(maximum cut)[34]；最短路——最长路(longest path)[47]等等。本文中将要详细讨论的逆目标优化问题包括懒惰官僚排序问题(Lazy Bureaucrat Scheduling)[3]；拖沓工人排序问题(ProcrastinatorScheduling)[10]；极大化资源装箱问题(Maximum Resource Bin Packing)[12；13]以及逆目标箱覆盖问题(Lazy Bin Covering)等。本文将就这几个问题进行算法及复杂性方面的研究。 全文共分六章，第一章主要介绍一些组合优化及算法方面相关的概念和预备知识。 第二章简要综述近年来与本文相关的逆目标优化问题的若干成果，并列举了本文得到的一些主要结果。 在第三章中，研究了懒惰官僚的排序问题(Lazy Bureaucrat Schedul-ing Problem)。主要考虑在单台机下，工件截止时间相同的懒惰排序问题(Common Deadline Lazy Bureaucrat Scheduling)，并且假设工件在加工过程中是不可中断的。在离线情况下，们证明了算法SJF(Shortest Job First)对于目标函数[min-time-spent]其最坏情况界仍然是2，解决了文献[23]中提出的公开问题。进一步的，对于目标函数[min-time-spent]和[min-makespan]，分别设计了两个多项式时间近似方案(Polynomial Time Approximation Scheme)，A<,k>和B<,k>。对于任给的正整数尼，该近似方案的最坏情况界至多是1+l/后。最后我们证明了即使工件的到达时间和截止时间均相同，懒惰官僚排序问题对于若干目标函数仍然是NP困难的。对于在线情况下的懒惰官僚排序问题，同样假设所有工件具有同一个截止时刻。我们给出了一个算法A，其竞争比为(<平方根5+1)/2，并且证明了它就是最优的在线算法。 第四章中研究了几个有关装箱问题的逆目标优化模型。首先证明了极大化资源装箱问题(Maximum Resource Bin Packing Problem)是NP困难的，解决了文献[12；13]中提出的公开问题；并且证明了FFI(First Fit Increasing)算法是绝对比意义下最好的算法，其最坏情况界为3/2。接下来我们考虑了逆目标的箱覆盖问题和带限制的Open-end装箱问题，分别指出了它们是NP难的，并设计出了相应的最好的近似算法。尤其对于逆目标箱覆盖问题，我们纠正了Lin等人在[51]中关于问题计算复杂性的证明。 第五章研究了拖沓者的排序问题(Procrastinator Scheduling Problem)。对于离线情况下，即使工件的初始速度不为零，我们证明仍存在一个多项式时间算法LRTB<+>可以极小化目标函数[min-time-spent]。我们还考虑了在线情况下工件的最大延迟比问题，指出只要采用α-Delay算法，4就是可以达到的最好的最大延迟比。 第六章为后记。简要的总结了一下本文的工作，讨论了未来的研究方向以及一些公开问题。