《算法设计》第15章-动态规划—装配线调度问题

骑猪看日落 2022-08-13 10:28 184阅读 0赞

动态规划---装配线调度

子问题的最的解

f1\[j\] = e1+a1,1 如果j=1

min(f1\[j-1\]+a1,j，f2\[j-1\]+t2,j-1+a1,j) 如果j>=2

f2\[j\] = e2+a2,1 如果j=1

min(f2\[j-1\]+a2,j，f1\[j-1\]+t1,j-1+a2,j) 如果j>=2

原问题的解

f\* = min(f1\[n\] +a1,f2\[n\] +x2)

伪代码

Fastest-Way(a, t, e, x, n)

f1\[1\] = e1 + a1,1

f2\[2\] = e2 + a2,1

for j=2 to n

do if f1\[j-1\] + a1,j < = f2\[j-1\] + t2,j-1 + a1,j

then f1\[j\] = f1\[j-1\] +a1,j

L1\[j\] = 1 //上面显示，通过S1\[j\]装配点最优解是在前一个装配点S1\[j-1\]最优解基础上得到的，

所以，Li\[j\]记录的是在最优解情况下，在第i生产线的j点的前一个装配点j-1所在的 生产线号

else f1\[j\] = f2\[j-1\] +t2,j-1 + a1,j

L1\[j\] = 2

if f2\[j-1\] + a2,j < = f1\[j-1\] + t1,j-1 + a2,j

then f2\[j\] = f2\[j-1\] +a1,j

L2\[j\] = 2

else f2\[j\] = f1\[j-1\] +t1,j-1 + a2,j

L2\[j\] = 1

if f1\[n\] +x1 <= f2\[n\] +x2

then f\* = f1\[n\] +x1

L\* = 1

else f\* = f2\[n\] + x2

L\* = 2

end

Print-stations (L, L\*, n)

i = L\*

print "line" + i + ",station " + n

for j = n downto 2

do i = Li\[j\]

print "line" + i + ", station " + j-1

end

[详细参考：http://www.cnblogs.com/Anker/archive/2013/03/09/2951785.html][http_www.cnblogs.com_Anker_archive_2013_03_09_2951785.html]

[http_www.cnblogs.com_Anker_archive_2013_03_09_2951785.html]: http://www.cnblogs.com/Anker/archive/2013/03/09/2951785.html

发表评论取消回复

表情：

评论列表（有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读

相关基于遗传算法的装配线调度优化

基于遗传算法的装配线调度优化装配线调度是在制造业中常见的优化问题之一。通过合理安排任务的顺序和分配资源，可以提高生产效率并降低成本。遗传算法是一种启发式优化算法，可用于解决

忘是亡心i/ 2024年03月03日 07:54/ 0 赞/ 123 阅读

相关【算法设计与分析】第四章动态规划

动态规划的基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。基

痛定思痛。/ 2023年07月18日 09:23/ 0 赞/ 65 阅读

相关动态规划算法设计字符串比较问题_「Javascript算法设计」× 动态规划与回溯算法...

目录：分而治之算法动态规划回溯算法分而治之算法分而治之算法是算法设计的一种方式，它将一个问题分成多个和原问题相似的小问题，递归解决小问题，

小灰灰/ 2023年01月12日 11:35/ 0 赞/ 129 阅读

相关《算法导论》第15章-动态规划之0-1背包问题

参考文章：[http://blog.csdn.net/yeepom/article/details/8712224][http_blog.csdn.net_yeepom_art

深藏阁楼爱情的钟/ 2022年08月13日 11:44/ 0 赞/ 188 阅读

相关《算法设计》第15章-动态规划—装配线调度问题

动态规划---装配线调度子问题的最的解 f1\[j\] = e1+a1,1 如果j=1 min(f1\[j-1\]+a1,j，f2\[j-1\]+t2,j-1+a1,j

骑猪看日落/ 2022年08月13日 10:28/ 0 赞/ 185 阅读

相关第三章动态规划

学习要点 -------------------- 理解动态规划的概念掌握动态规划算法的基本要素（1）最优子结构性质（2）重复子问题性质掌握设计

冷不防/ 2022年08月01日 00:22/ 0 赞/ 207 阅读

相关流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）C++实现

流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）问题描述：有二条流水线，每条流水线都有n个站，流水线1,2站j的处理功能相同，但处理时间可能不同，每

客官°小女子只卖身不卖艺/ 2022年06月18日 11:09/ 0 赞/ 167 阅读

相关流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）C++实现...

流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）问题描述：有二条流水线，每条流水线都有n个站，流水线1,2站j的处理功能相同，但处理时间可能不同，每个

水深无声/ 2022年05月15日 13:15/ 0 赞/ 151 阅读

相关流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）C++实现...

流水线调度最优问题（装配线调度问题）动态规划 O(n)时间（线性时间）问题描述：有二条流水线，每条流水线都有n个站，流水线1,2站j的处理功能相同，但处理时间可能不同，每个

雨点打透心脏的1/2处/ 2022年05月15日 13:14/ 0 赞/ 156 阅读

相关动态规划之装配线调度理解

一.装配线事例 ![这里写图片描述][20160816174044374] ![这里写图片描述][20160816174059374] 二.例题分析动态规划适

喜欢ヅ旅行/ 2021年06月10日 20:41/ 0 赞/ 390 阅读