关键词: 批处理, 提前拖期, 动态规划, 差分进化算法

Abstract: This paper considers a single batch scheduling problem,where the batch processing machine has restricted capacity.The processing time of a batch is equal to the longest time among all the jobs contained in the batch.All jobs have different sizes,different earliness and tardiness punishing weights,but the same due date which is unrestri-ctively late.The objective is to minimize the sum of weighted earliness and tardiness of all jobs,which are the absolute deviations of completion times from the common due date. This problem is proved to be NP-complete.In this paper,we identify several properties of the optimal scheduling.According to these properties,we propose a hybrid discrete differential evolution algorithm (HDDE)based on differential evolution(DE)and dynamic programming(DP)to solve this scheduling problem.Compared to three traditional heuristicalg orithm(genetic algorithm(GA),simulated annealing (SA),it erated greedy(IG)),HDDE shows a subst antially better global searching ability for the batch scheduling problem.

Key words: batch scheduling, earliness and tardiness, dynamic program, differential evolution algorithm