带成组加工的二阶段柔性流水作业问题  

Two-stage Flexible Flowshop Scheduling Problems with a Batch Processor on Second Stage

作　　者：何龙敏[1] 孙世杰[1] 罗润梓[2] 

机构地区：[1]上海大学数学系,上海200444 [2]南昌大学数学系,南昌330031

出　　处：《工程数学学报》2008年第5期829-842,共14页Chinese Journal of Engineering Mathematics

基　　金：国家自然科学基金(60874039);上海大学创新基金

摘　　要：本文仔细剖析混杂二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段由一台批处理机M组成,并以最大完工时间Cmax为极小化目标函数。我们证明了该类问题除一种情况有多项式时间可解外,其余情况为(强)NP-hard的。文中对所有(强)NP-hard情况均给出了近似算法并作了性能比分析。This paper considers the batch scheduling problem in a two-stage hybrid flowshop which consists of m identical parallel machines in stage 1 and a batch processor in stage 2. The processing time of a batch is defined as the largest processing time of the jobs contained in that batch. The criterion is to minimize the makespan, the time by which all operations of jobs have been finished. Many practical problems can be modeled as such a schudling problem. For example： cut the steel rods into short bars and process these bars into gear roughs on a group of dedicated parallel machines; heat-treat these gear roughs in an oven to delete the processing stress. This scheduling problem is NP-hard in general. We divide it into twelve subcases. Except for the following special case： the same batch processing time of all the jobs in the second stage is not less than the largest processing time of the jobs in the first stage,and the upper bound of the number of the jobs can be processed simultaneously in the second stage is not greater than m while m is less than the number of jobs, their NP-hardness has been proved or pointed out, corresponding approximation algorithms are designed and their worst-case performances are estimated.

关 键 词：排序 柔性流水作业 同型机 批处理机 复杂性 近似算法 

分 类 号：O223[理学—运筹学与控制论]