两台机器流水作业中带成组加工的最大迟后问题

Minimizing the Maximum Lateness on a Two Machine Flowshop with Batch Processors

考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为Lmax.文中指出该问题为NP-hard后给出了其多项式可解的特例并构造了相应的动态规划算法.

This paper considers the following problem: n jobs need to be processed on two machines (M_1,M_2) successively. The deadline for job j is d_j, and the processing times of job j on M_1, M_2 are a_j, b_j, respectively. Both machines are batch processors. This means n jobs are grouped into several batches on M_i, i=1,2, respectively, and the machines process the jobs in same batch simultaneously. The processing time of a batch is equal to the longest processing time of all the jobs in this batch. Thus all the jobs in same batch are processed in the same length of time on the given machine, and the jobs will be also shifted in batches. We take the maximum lateness as our objec function for minimization. After pointing out that this scheduling problem is NP-hard, we give some special cases that can be solved in polynomial time and construct the corresponding dynamic programming.