某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n(Sij，i=1或2，j=1，2，…，n)，两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同(aij，i=1或2，j=1，2，…，n)。汽车底盘开始到进入两条装配线的时间(e1，

admin2019-07-12 26

问题某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n(S_ij，i=1或2，j=1，2，…，n)，两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同(a_ij，i=1或2，j=1，2，…，n)。汽车底盘开始到进入两条装配线的时间(e₁，e₂)以及装配后到结束的时间(X₁X₂)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间(t_ij，i=1或2，j=2，…，n)。现在要以最快的时间完成一辆汽车的装配，求最优的装配路线。
分析该问题，发现问题具有最优子结构。以L1为例，除了第一个工位之外，经过第j个工位的最短时间包含了经过L1的第，j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，如式(1)。装配后到结束的最短时间包含离开L1的最短时间或者离开L2的最短时间如式(2)。

由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间，该问题具有重复子问题的性质，故采用迭代方法求解。
该问题采用的算法设计策略是(62)，算法的时间复杂度为(63)。
以下是一个装配调度实例，其最短的装配时间为(64)，装配路线为(65)。

(63)

选项 A、O(lgn)
B、O(n)
C、O(n²)
D、O(nlgn)

答案B

解析

转载请注明原文地址:https://kaotiyun.com/show/DICZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

关于在I／O设备与主机间交换数据的叙述，__________是错误的。(2008年下半年试题)

关于MAC地址的说法，__________是正确的。

ATM高层定义了4类业务，压缩视频信号的传送属于__________。(2010年上半年试题)

在Windows环境下，租约期满后，DHCP客户端可以向DHCP服务器发送一个_____________报文来请求重新租用IP地址。

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(1)

总线复用方式可以__________。(2011年下半年试题)

在Linux中，_____________是默认安装DHCP服务器的配置文件。

根据这张通知书所提供的信息，设计了一个E-R模型，如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型，要求标注主码和外码。

阅读以下说明和C程序，填入(n)外。[说明]以下C程序实现了将字符串转化为浮点数的功能。例如字符串“1234567”转化为浮点数1234567；字符串“100.02035”转化为浮点数100.02035；字符串“-100.02035”转化为

在中断响应过程中，CPU保护程序计数器的主要目的是______。

对建筑物适用的基本要求包括()。

铁路列车高速运行下，轮对的轴温会因摩擦升温，造成燃轴、切轴事故的发生，为保证铁路行车的安全，在铁路干线上，应设红外线轴温探测网，轴温探测站的向距一般按()km设置。

根据《安全生产违法行为处罚办法》的规定，各级政府安全生产监管部门可以实施（）处罚行为。

建筑工程一切险的被保险人可以包括(　　)。

半导体热敏电阻有哪些特点?

能够表明工作内容和工作任职者资格的文件是()。

中外合作经营企业成立后，改为委托合作各方以外的第三人经营管理的，应当履行的程序是()。

乌龙茶也称“青茶”，属半发酵茶，制作方式介于红茶与绿茶之间。()

France’smethodsforincreasingfamilysizegiveusa(n)______astowhatmightbedonetoencouragesmallerfamilies.

A—officepinB—officeclockC—penholderD—notepaperE—globeF—staplerG—memoholderH—paperfastenerI—tapedispenserJ—letter

软件设计师上午基础知识考试

软考中级

关于在I／O设备与主机间交换数据的叙述，__________是错误的。(2008年下半年试题)

关于MAC地址的说法，__________是正确的。

ATM高层定义了4类业务，压缩视频信号的传送属于__________。(2010年上半年试题)

在Windows环境下，租约期满后，DHCP客户端可以向DHCP服务器发送一个_____________报文来请求重新租用IP地址。

网络配置如下图所示，为路由器Routerl配置访问网络1和网络2的命令是(1)。路由配置完成后，在Routerl的(2)可以查看路由，查看路由采用的命令是(3)。(1)

总线复用方式可以__________。(2011年下半年试题)

在Linux中，_____________是默认安装DHCP服务器的配置文件。

根据这张通知书所提供的信息，设计了一个E-R模型，如图12-6所示。请将(n)处补充完整。将问题1中的E-R模型(图12-6)转换成4个关系数据模型，要求标注主码和外码。

阅读以下说明和C程序，填入(n)外。[说明]以下C程序实现了将字符串转化为浮点数的功能。例如字符串“1234567”转化为浮点数1234567；字符串“100.02035”转化为浮点数100.02035；字符串“-100.02035”转化为

在中断响应过程中，CPU保护程序计数器的主要目的是______。

对建筑物适用的基本要求包括()。

铁路列车高速运行下，轮对的轴温会因摩擦升温，造成燃轴、切轴事故的发生，为保证铁路行车的安全，在铁路干线上，应设红外线轴温探测网，轴温探测站的向距一般按()km设置。

根据《安全生产违法行为处罚办法》的规定，各级政府安全生产监管部门可以实施（）处罚行为。

建筑工程一切险的被保险人可以包括( )。

半导体热敏电阻有哪些特点?

能够表明工作内容和工作任职者资格的文件是()。

中外合作经营企业成立后，改为委托合作各方以外的第三人经营管理的，应当履行的程序是()。

乌龙茶也称“青茶”，属半发酵茶，制作方式介于红茶与绿茶之间。()

France’smethodsforincreasingfamilysizegiveusa(n)______astowhatmightbedonetoencouragesmallerfamilies.

A—officepinB—officeclockC—penholderD—notepaperE—globeF—staplerG—memoholderH—paperfastenerI—tapedispenserJ—letter

建筑工程一切险的被保险人可以包括(　　)。