Research on Unbounded Parallel-Batch Scheduling with Jobs Having Set-Up Times  

工件有安装时间的无界平行分批排序研究

作　　者：GAO Yuan DANG Jia-rui PENG Juan 高园;党佳瑞;彭娟(School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China)

机构地区：[1]School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China

出　　处：《Chinese Quarterly Journal of Mathematics》2022年第4期422-429,共8页数学季刊（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant No.11901539)。

摘　　要：We study the scheduling on an unbounded parallel-batch machine with jobs having set-up times to minimize a regular objective function which is either of the sumform or of the max-form.As we know,in the existing literature,the research about parallel-batch scheduling does not consider the set-up times of jobs.However,the set-up times of jobs are widely presented in practical applications.Each job considered in this paper has a set-up time.The set-up time of each batch is equal to the maximum set-up time of all jobs contained in the batch,and the processing time of each batch is equal to the longest processing time of the jobs contained in the batch.Depending on the different definitions of the completion time of a job,we consider two types of jobs:batch jobs and drop-line jobs.For batch jobs,the completion time of a job is given by the completion time of the batch containing this job.For drop-line jobs,the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job.In this paper,we give pseudo-polynomial time algorithms for the above scheduling problems in which the jobs have agreeable processing times and set-up times.In addition,when the objective functions are the total weighted completion time,the maximum lateness,and the maximum cost,we present a polynomial time algorithm,respectively.

关 键 词：SCHEDULING Parallel-batch Set-up time Agreeable ALGORITHM 

分 类 号：O187.1[理学—数学]