具有独立安装时间和恶化效应的单机成组排序问题研究

Research on single-machine group scheduling with independent setup times and deterioration effect

研究具有恶化效应且带有准备时间的单机成组排序问题,其中同一组内工件的加工时间具有简单线性恶化效应和独立的常数准备时间,各组之间的调整时间为独立的常数安装时间。目标是确定同一组内工件的排列顺序和各组之间的排列顺序使所有工件的最大完工时间最小。对此问题给出了一个下界和一个启发式算法,即上界,从而可以用分支定界算法来求此问题的最优解。

This paper considers a single-machine group scheduling problem with deterioration effect and ready times, where the processing time of a job within each group is a simple linear deterioration effect, ready time of a job within each group is an independent constant, and the setup times of groups are independent constants. Our objective is to determine the schedule of jobs within each group and the schedule of groups to minimize the make-span. A branch-and-bound algorithm incorporating with a lower bound and a heuristic algorithm（ i. e. , an upper bound） are proposed to find the optimal solution for the problem.