论文部分内容阅读
本文研究了一种新的客户订单调度问题。假设有n 个客户订单需要在一台机器上加工，每个订单中都有k 个不同的工件。当工件被加工完后即可运给客户。同一个订单中的工件按照链式的先后顺序分期交付，订单中每个工件的交货期等于它紧前工件的完成时间加上一个时间间隔，即相对提前期。目标函数为最小化最大工件延迟。我们证明了当全部订单中只有两种工件时，该问题为普通的NP 困难问题，以及当全部工作的相对提前期都相同时，该问题为强的NP 困难问题。