调整时间与顺序相关的等同并行机调度

Identical Parallel Machines Scheduling with Sequence-dependent Setup Times

调整时间与顺序相关的等同并行机调度在生产服务业与制造业中有着十分广泛的应用背景,具有计算复杂性的主要特点。调整时间与顺序相关的等同并行机调度是将被加工工件集的各工件分配给等同并行机资源,并安排工件的加工次序。它是决策的一种形式,其目的是优化一个或多个目标。研究以最小化被加工工件最大完工时间为目标的调整时间与顺序相关的等同并行机调度,建立该问题的数学规划模型,根据问题的结构特点开发基于两段式染色体表达的遗传算法以获得该问题的近似最优解;在所建立数学规划模型的基础上,引入所求解问题的下界对近似最优解的质量进行评价。对具有不同规模的问题实例进行计算试验,计算结果表明所设计的遗传算法能够在可接受的计算时间内获得合理的解。

Identical parallel machines scheduling with sequence-dependent setup time is extensively applied in productive service and manufacturing industry and its main characteristic is computational complexity.Identical parallel machines scheduling with sequence-dependent setup time is to allot a set of jobs to be processed into identical parallel machines and sequence the jobs on each machine.It is a type of decision making with the purpose of optimizingsingle objective or multiple objectives.Identical parallel machines scheduling with sequence-dependent setup time to minimize the maximum job completion time is studied.The problem is formulated as a mathematical programming model.According to the structure characteristic of the problem,a genetic algorithm based on two-part chromosome representation is developed to obtain near optimal solutions.Based on the proposed mathematical programming model,a lower bound for the problem is introduced to evaluate the quality of near optimal solutions.Computational experiments are conducted on instances of different sizes,and the computational results show that the designed genetic algorithm can obtain reasonable solutions within an acceptable computational time.