关键词: 车间作业调度, 复杂随机来料, 批量流, 样本均值近似, Benders分解, 禁忌搜索

Abstract: The production scheduling problem of multiple types and batches of jobs is a crucial issue in current workshop manufacturing.In the real production environment,it is necessary to consider the setup time of machines during sub-lot switching and the highly complicated random arrival time of different jobs,which cause great difficulties in production scheduling.Research on such issues has not yet begun.Based on sample average appropriation method,an optimized objective model of lot streaming with setup time and random arrival of jobs was built for minimizing the makespan.Meanwhile,Benders decomposition was used to solve the problem precisely and the heuristic algorithm combing Benders decomposition and tabu search was designed to solve the problem.These algorithms could implement parallel optimization of job splitting and scheduling problems.The effectiveness of the proposed method was verified by numerical experiments.

Key words: job-shop scheduling, complex random arrival, lot streaming, sample average appropriation, Benders' decomposition, tabu search