加工时间可控的同时加工排序问题  

Scheduling a Batch Processing Machine with Controllable Processing Times

作　　者：柏孟卓[1] 唐国春[1] 

机构地区：[1]同济大学应用数学系,上海200092

出　　处：《上海第二工业大学学报》2006年第1期15-20,共6页Journal of Shanghai Polytechnic University

基　　金：国家自然科学基金项目(No.10371071);上海市自然科学基金项目(No.03ZR14039);上海市教育委员会基金项目(No.04RB06)

摘　　要：同时加工排序和可控排序是两类很重要的现代排序模型,有着深刻的实际背景和广阔的应用前景,已经取得许多有意义的成果,然而,还没有看到把两者结合起来的研究。把这两类排序模型相结合,讨论加工时间可控的同时加工排序问题:工件可以有不同的加工时间,每个加工时间对应一个控制费用,所有工件在单台机器上平行同时加工,即同时加工的一批工件的加工时间等于这批工件中所有工件加工时间的最大者;分别使误工工件个数和最大延迟加上加工时间可控所需费用的总和为最小作为优化的目标。讨论了这两个问题的最优解的性质,并以此为基础提出了相应的动态规划算法。Because of the extensive applications and realistic meaning, the problems of scheduling on a batch machine gets much attentions since the first paper about it been published. There are many results about it. The controllable scheduling is also an important scheduling model. This paper, combines these two models, study scheduling a batch processing machine with controllable processing times. The control!ab!e processing times of each job are discrete. Each processing time has its own controllable cost. All the jobs are scheduled on a single machine that means the processing time of a batch is equal to the largest one in the batch. Problems to minimize the number of tardy jobs or the maximum lateness plus costs of controlling the processing times are discussed respectively. Properties of optimal schedules are analyzed and two efficient dynamic programming algorithms are presented.

关 键 词：同时加工排序 可控 动态规划 

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