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

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

作　　者：陈跃[1] 孙世杰[1] 宋政芳[1] 何龙敏[1] 

机构地区：[1]上海大学数学系,上海200436

出　　处：《应用科学学报》2004年第2期247-251,共5页Journal of Applied Sciences

摘　　要：考虑分批加工中的流水作业问题:且工件在两台机器间作成批转移,目标函数为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.

关 键 词：排序 批处理机 最大迟后 强NP-hard 多项式可解 流水作业 成组加工 

分 类 号：TH162.1[机械工程—机械制造及自动化] O223[理学—运筹学与控制论]