`
songzi0206
  • 浏览: 158858 次
  • 性别: Icon_minigender_1
  • 来自: 上海
博客专栏
Group-logo
All are from ...
浏览量:33817
Group-logo
Programming w...
浏览量:19683
社区版块
存档分类
最新评论

动态规划之装配线问题

 
阅读更多

 

/**

 * 动态规划之装配线问题:

 * 有两条装配线L1和L2,每条装配线上有n个站,将装配线i(=1或2)的第j个站表示为S[i][j].装配线1和2的第j个站功能相同,但是加工的时间不同,设S[i][j]站得时间为a[i][j]

 * 一个产品进入生产线i的时间为e[i],完成后离开生产线i的时间为x[i]

 * 一个产品在同一条装配线上从上一站完成后转移到下一站的时间为0,但是从一条装配线L[i]上得一个站S[i][j]转移到另一条装配线上得站S[i'][j+1]需要时间为t[i][j]

 * 

 * 思路:通过S[i][j]站最快的路线,必定是通过S[1][j-1]站最快或者通过S[2][j-1]站最快的路线之一。

 * 设f[i][j]表示从入口到站S[i][j]的最快时间,则我们要求的最小时间

 * f = min(f[1][n]+x[1],f[2][n]+x[2])

 * f[1][1] = e1 + a[1][1],  f[2][1] = e2 + a[2][1],进一步有:

 *       f[1][j] = e1+a[1][1]  if j == 1

 *                 min(f[1][j-1]+a[1][j], f[2][j-1]+t[2][j-1]+a[1][j]) if j >= 2

 *                 

 *       f[2][j] = e2 + a[2][1]  if j==1

 *                 min(f[2][j-1]+a[2][j], f[1][j-1]+t[1][j-1]+a[2][j]) if j >= 2

 *                 

 *  在计算过程中,我们需要填满一张 2 * n 的表格为f[1][1....n]和f[2][1....n]的值

 *  此外,我们再定义l[i][j]来记录经过站S[i][j]的上一站S[i][j]的i值1 或者 2,通过这个表的值最终能得到最优装配路线

 * @author song

 *

 */

 

 

/**

* @param a 通过每一站的时间,a[i][j]为通过i+1(因为数组下标从0开始记,所以i = 0,1)条路线的j+1站得时间,第一维度2, 第二维度 n,j=0,1,...n-1

* @param t 从一条线路转到另一条路线的时间,t[i][j]为从第i+1条路线的第j+1站转移到另一条路线的j+2站所需的时间,第一维2(i = 0,1), 第二维n - 1(j=0,1,...n-2)

* @param e 长度为2的数组,e[0]表示进入到站S[1][1]的的时间,e[1]表示进入到第二条路线第一站的时间

* @param x 长度为2的数组,x[0]表示离开第一条路线最后一站的时间,x[1]表示离开第二条路线最后站的时间

* @param n 装配线的长度

*/

public static AssembleResult fastestWay(int[][] a, int[][] t, int[] e, int[] x, int n){
		//用来存经过每一站的最优时间
		int[][] f = new int[2][n];
		//用来记录走过的路线
		int[][] l = new int[2][n-1];
		
		//初始化
		f[0][0] = e[0] + a[0][0]; //经过第1条装配线第一站的时间
		f[1][0] = e[1] + a[1][0]; //经过第2条装配线第一站的时间
		
		for( int i = 1; i < n; ++i){
			//循环计算f[0][i]和f[1][i]
			if( f[0][i-1]+a[0][i] < f[1][i-1] + t[1][i-1] + a[0][i]){
				f[0][i] = f[0][i-1]+a[0][i];
				l[0][i-1] = 1;
			}else{
				f[0][i] = f[1][i-1] + t[1][i-1] + a[0][i];
				l[0][i-1] = 2;
			}
			
			if(f[1][i-1] + a[1][i] < f[0][i-1] + t[0][i-1] + a[1][i]){
				f[1][i] = f[1][i-1] + a[1][i];
				l[1][i-1] = 2;
			}else{
				f[1][i] = f[0][i-1] + t[0][i-1] + a[1][i];
				l[1][i-1] = 1;
			}
		}
		int resultV = 1;
		int theLastLineOfPath = 1;
		if( f[0][n-1] + x[0] < f[1][n-1] + x[1]){
			resultV = f[0][n-1] + x[0];
		}else{
			resultV = f[1][n-1] + x[1];
			theLastLineOfPath = 2;
		}
		return new AssembleResult(l,theLastLineOfPath, resultV);
	}
	
	static class AssembleResult{
		int lastLineOfPath;
		int[][] path;
		int value;
		public AssembleResult(int[][] path,int lastLineOfPath, int value) {
			this.path = path;
			this.lastLineOfPath = lastLineOfPath;
			this.value = value;
		}
		@Override
		public String toString() {
			return "AssembleResult path=[" + getThePath() + ", value="
					+ value + "]";
		}
		
		public String getThePath(){
			StringBuilder sb = new StringBuilder();
			int lineNum = lastLineOfPath;
			int stationNum = path[0].length + 1;
			sb.append("(line").append(lineNum).append(" station").append(stationNum).append(")");
			for( int i = path[0].length; i > 0 ; --i){
				lineNum = path[lineNum-1][i-1];
				stationNum = i;
				sb.insert(0, "(line"+lineNum+" station"+stationNum+") -->");
			}
			return sb.toString();
		}
	}

 

测试:

 

public static void main(String[] args){
		int[][] a = new int[][]{{7,9,3,4,8,4},{8,5,6,4,5,7}};
		int[][] t = new int[][]{{2,3,1,3,4},{2,1,2,2,1}};
		int[] x = new int[]{3,2};
		int[] e = new int[]{2,4};
		int n = 6;
		AssembleResult r = fastestWay(a, t, e, x, n);
		System.out.println(r.toString());
	}

 

结果:

 

AssembleResult path=[(line1 station1) -->(line2 station2) -->(line1 station3) -->(line2 station4) -->(line2 station5) -->(line1 station6), value=38]


分享到:
评论

相关推荐

    经典动态规划:装配线问题

    《经典动态规划:装配线问题》是动态规划应用的一个典型实例,通过解决装配线上的最优路径选择问题,展现了动态规划的强大功能。 #### 装配线问题概述 装配线问题通常涉及到两个或多个平行的装配线,每条线上有...

    动态规划解装配线调度问题

    ### 动态规划解决装配线调度问题 #### 问题背景及描述 在现代制造业中,装配线调度问题是一项常见的挑战,特别是在汽车制造业中。本文旨在介绍如何应用动态规划方法来解决此类问题,以达到最优化的目标。具体而言...

    论文研究-基于动态规划的装配线物料搬运节能调度方法.pdf

    论文研究-基于动态规划的装配线物料搬运节能调度方法.pdf, 为有效提升混流装配线的生产效率与环境效益,提出了装配线多载量小车物料搬运节能调度方法.以最小化最大线边...

    装配线 动态调度

    【装配线动态调度】是指在汽车工厂中,利用动态规划算法优化装配线的作业顺序,以达到最小化汽车从进入工厂到出厂总时间的目标。在这个问题中,工厂有两条装配线,每条线由n个装配站组成。每个站Si,j对应一定的装配...

    关于动态规划实现装配线调度的算法

    关于动态规划实现装配线调度的算法,刚看过算法导论之后把书上的伪代码变为原代码。。

    动态规划--工厂装配线c++代码

    算法导论第十五章动态规划--工厂装配线c++代码实现

    装配线调度问题实现(C语言实现)

    4. 动态规划:在某些情况下,装配线调度问题可以用动态规划方法解决。通过建立状态转移方程,可以找到最优的调度策略,避免重复计算。 5. 并行处理:如果系统资源允许,可以利用多核处理器的并行计算能力,通过并发...

    装配线调度问题算法导论15章

    本段代码提供了一个基于动态规划方法解决装配线调度问题的具体实现方案。通过对数据结构的定义、关键函数的设计以及主程序流程的控制,有效地解决了装配线调度问题,并能够输出最优路径。这种方法不仅适用于简单的双...

    北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java

    利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以文本文件的形式存储, 即所有的数据由文本文件读入。 利用动态规划算法实现0-1背包问题或装配线调度问题。(二选一) 要求测试数据以...

    规划阶段的自动化装配线仿真与优化.pdf

    规划阶段的自动化装配线仿真与优化是指在装配线实际搭建之前,通过仿真软件对装配线的设计方案进行模拟和评估,从而在虚拟环境中发现潜在的问题,并对方案进行优化的过程。本文档的主题“规划阶段的自动化装配线仿真...

    算法--动态规划课件(动态规划实例加基础)

    动态规划算法的基本思想是将问题broken down into smaller sub-problems,解决每个子问题,然后合并子问题的解来得到原问题的解。 动态规划算法的基本要素包括: 1. 最优子结构性质:子问题的解可以合并成原问题的...

    该算法是一种概率方法,用于逼近简单装配线平衡问题的全局最优值_AMPL_代码_下载

    AMPL是一种高级建模语言,用于描述优化问题的结构,支持线性、非线性、整数和动态规划模型。在装配线平衡问题中,可以利用AMPL来声明变量、定义约束和目标函数,然后调用外部求解器来寻找最优解。在提供的压缩包文件...

    本科生算法设计与分析中动态规划算法的讲稿

    动态规划是一种解决问题的方法,尤其适用于优化问题,如装配线调度或矩阵链乘法。它并非特定的算法,而是一种策略,类似于分治法。动态规划的核心在于“编程”指的是使用表格来存储中间结果,而非传统的计算机编程。...

    AGV装配线技术方案.doc

    AGV装配线应具备适应不同轴距车型的能力,这意味着AGV路径规划和工作台设计需具有足够的灵活性,以应对车身尺寸变化。 9. **AGV动态装配解决方案** 针对生产流程中的动态变化,AGV系统应配备先进的调度算法,实时...

    算法与程序设计:第3章 动态规划2.pptx

    - **装配线调度问题**:在多个工作站之间安排任务,以最小化总完成时间。动态规划可以找到最优的作业顺序。 - **凸多边形最优三角剖分**:将凸多边形分割成尽可能少的三角形。动态规划可以确保每一步都是最优的,以...

    常见动态规划源代码锦集

    里面有很详细的思路和当时的一些理解 欢迎大家指正 包括 斐比那契数列(递归,迭代) 数学三角形问题(递归,迭代) 0-1背包问题(包括递归版和两种... 活动选择问题(包括动态规划的递归和迭代,贪心算法的递归和迭代共四种)

    1.9明匠智能-无锡X通装配线可视化方案(共39页).zip

    《明匠智能-无锡X通装配线可视化方案》是一份深度探讨智能制造与MES解决方案的专题报告,共计39页,旨在提升生产线的效率与透明度。该方案由明匠智能公司精心打造,针对无锡X通装配线的具体需求,提供了一整套先进的...

    assemblyLineProblem:动态规划 - 流水线算法

    通过这种方式,我们可以利用Java的灵活性和动态规划的强大能力,有效地解决装配线问题,优化生产效率,减少等待时间,从而提高整体的生产效益。 在实际应用中,可能还需要考虑额外的因素,如工作站的容量限制、...

Global site tag (gtag.js) - Google Analytics