算法上机(三) 动态规划解决装配线排程(调度)问题

2024-01-20 05:10

本文主要是介绍算法上机(三) 动态规划解决装配线排程(调度)问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

一汽车厂有两条装配线,每条装 配线有n个工序站台,每条装配线的 第j个站台的功能相同,但是效率不一致,每条装配线的上线和下线时间表示为e1,e2和x1,x2。另外,切换线路也需要时间t1j,t2j。求如何充分利用两条装配线, 使得组装一辆汽车的时间短。
如图所示
在这里插入图片描述

解决方法

这里介绍两种方法。第一,蛮力法。简单易懂,时间复杂度高,不推荐。第二,动态规划法。比较难理解,但效率高。

蛮力法

用迭代的方法计算装配线排程 所有可能的组合情况,比较并选择出短时间的组合。由于每个站有两种可能,因此总共有2的n次方种可能,时间复杂度也为O(2^n)。

动态规划法

自底向上求解最优解。先求出到第i个站的最优解,再根据此求出第i+1个站的,直到第n个站,以及下线完成生产。有:f1[i] = min(f1[i-1]+a1[i],f2[i-1]+t2[i-1]+a1[i])。
其中,f1[i]表示在第一条线完成第i个站所需要的最短时间,a1[i]表示在第一条线第i个站加工需要的时间,t1[i]表示在第一条线第i个站加工完成后转到第二条线需要的时间。
代码如下。

#include <stdio.h>
#include <stdlib.h>const int n = 5;	//每条线工作站的数目 
int a1[n] = {7,9,3,4,8};	//元件在第一条线第i个站加工需要的时间 
int a2[n] = {8,5,6,4,5};
int e1=2,e2=4,x1=3,x2=6;	//e起始入线时间,x终止出线时间 
int t1[n-1] = {2,3,1,3};	//在第i个站换线需要的时间 
int t2[n-1] = {2,1,2,2};
int f1[n],f2[n];	// 动态规划,存储到第i个站的最短时间 
int l[2][n];	//存储路径 
int f,last;		//最终时间和路径 void fatestway(){f1[0] = e1+a1[0];l[0][0] =1;f2[0] = e2+a2[0];l[1][0] = 2;printf("%d,%d\n",f1[0],f2[0]);for(int i=1;i<n;i++){//f1[i] = min(f1[i-1]+a1[i],f2[i-1]+t2[i-1]+a1[i])if(f1[i-1]+a1[i]<f2[i-1]+t2[i-1]+a1[i]){f1[i] = f1[i-1]+a1[i];l[0][i] = 1;}else{f1[i] = f2[i-1]+t2[i-1]+a1[i];l[0][i] = 2;}//f2[i] = min(f2[i-1]+a2[i],f1[i-1]+t1[i-1]+a2[i])if(f2[i-1]+a2[i]<f1[i-1]+t1[i-1]+a2[i]){f2[i] = f2[i-1]+a2[i];l[1][i] = 2;}else{f2[i] = f1[i-1]+t1[i-1]+a2[i];l[1][i] = 1;}printf("%d,%d\n",f1[i],f2[i]);}if(f1[n-1]+x1<f2[n-1]+x2){f = f1[n-1]+x1;last = 1;}else{f = f2[n-1]+x2;last = 2;}
}
//递归调用,逆序打印出每个站在哪条线路 
void print(int i,int j){if(j==1){printf("Line:%d Station:%d\n",i,j);}else{print(l[i-1][j-1],j-1);printf("Line:%d Station:%d\n",i,j);}
}int main (void){fatestway();print(last,n);printf("总路线时间:%d",f);
}

这篇关于算法上机(三) 动态规划解决装配线排程(调度)问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/624880

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-