### 使用Python实现8台机器(M1-M8)的流水线作业调度算法 对于流水线作业调度问题，可以采用多种方法来求解最优或近似最优方案。一种常见的策略是遗传算法 (Genetic Algorithm, GA)，其能够有效地处理复杂的组合优化问题。 #### 遗传算法简介 遗传算法是一种模拟自然选择过程的全局搜索概率算法[^1]。该类算法通过模仿生物进化中的选择、交叉和变异机制，在给定范围内探索可能的最佳解决方案集合。针对特定应用领域调整这些操作的具体形式可提高解决问题效率。 下面展示了一个简单的基于GA框架下的Python程序实例用于解决具有八个阶段的任务分配至八台不同设备上的最小化总完成时间(Cmax)问题： ```python import random from deap import base, creator, tools, algorithms def evalCmax(individual): """评估个体适应度""" # 假设每个job在对应machine上的加工时间为固定值 processing_times = { 'M1': [random.randint(10, 20), ...], 'M2': [...], ... 'M8': [...]} makespan = [] for i in range(len(individual)): machine_name = f'M{i+1}' job_index = individual[i]-1 if not makespan: makespan.append(sum([processing_times[machine][job_index] for machine in list(processing_times)[:i+1]])) else: last_machine_time = sum([ processing_times[list(processing_times)[j]][individual[j]-1] for j in range(i)]) current_job_start = max(makespan[-1], last_machine_time) current_job_end = ( current_job_start + processing_times[machine_name][job_index]) makespan.append(current_job_end) return min(makespan), creator.create("FitnessMin", base.Fitness, weights=(-1.0,)) creator.create("Individual", list, fitness=creator.FitnessMin) toolbox = base.Toolbox() n_jobs = n_machines = 8 # 属性生成器定义 toolbox.register("indices", random.sample, range(1, n_jobs + 1), n_jobs) # 初始化函数注册 toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices) toolbox.register("population", tools.initRepeat, list, toolbox.individual) # 进化算子配置 toolbox.register("mate", tools.cxPartialyMatched) toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05) toolbox.register("select", tools.selTournament, tournsize=3) toolbox.register("evaluate", evalCmax) if __name__ == "__main__": pop_size = 300 cx_prob = 0.7 mut_prob = 0.2 generations = 40 population = toolbox.population(n=pop_size) hof = tools.HallOfFame(1) stats_fit = tools.Statistics(lambda ind: ind.fitness.values) stats_size = tools.Statistics(len) mstats = tools.MultiStatistics(fitness=stats_fit, size=stats_size) mstats.register("avg", numpy.mean) mstats.register("std", numpy.std) mstats.register("min", numpy.min) mstats.register("max", numpy.max) result_population, logbook = algorithms.eaSimple( population, toolbox, cxpb=cx_prob, mutpb=mut_prob, ngen=generations, halloffame=hof, verbose=True, stats=mstats) print('Best Individual:', hof[0]) print('Minimum Makespan:', hof[0].fitness.values[0]) ``` 此代码片段展示了如何利用DEAP库构建并运行一个基本版本的遗传算法以找到使最大完工时间最小化的任务序列安排方式。注意这里为了简化起见假设每项工作在同一台机器上的执行耗时不随顺序变化而改变；实际情况下可根据具体需求修改`evalCmax()`函数内部逻辑来反映更复杂的关系模型。