论文部分内容阅读
在经典排序问题中，所有的工件都必需被接受且加工。然而，在很多实际生产情况下，特别是有大批量订单时，接受加工所有的订单可能会导致订单的延误，由此会带来高昂的存贮和延误费用。因此，一些工厂可能会把部分订单外包或者拒绝。带拒绝的排序问题无论是实践方面还是理论方面都非常有意义，所以在过去十几年中吸引大量研究者的关注。 在本课题中，首先考虑这样一个带有拒绝工件的单机排序问题。有n个工件，每个工件都有一个确定的到达时间，加工时间和拒绝费用。接受加工一部分工件并且对这些工件进行排序。这个问题是一般NP-困难的。本文为这个问题建立一个混合整数规划模型，并设计了一个分支定界的算法。然后给出了一个1.618-近似算法。通过数值模拟实验，来观测分支定界算法的效果。同时，也给出了近似算法的模拟结果。随后，将这个问题推广到平行机上，并给出了一个2-近似算法，同样通过模拟实验来检验这个算法的有效性。