订单带多类工件时的最大迟后问题

Minimizing the Maximum Lateness of Order with Multiple Job Classes

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。

This paper considers a single machine sequencing problem with multiple job classes. Each customer places an order with several jobs. The jobs in total n can be grouped into k different classes. When the machine is changed processing the jobs in a class to jobs in a different class, say class i, a nou-productive time Si is required for setups. There exists a due date for each order. The objective function considered is to minimize the maximum lateness of order. Corresponding to three different models of this sequencing problem, this paper gives a polynomial time algorithm, a branch and bound algorithm and a dynamic programming, respectively.