数学建模--车间作业调度问题
一、二维背包问题
一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。 它的状态变量有两个因素:一个是重量，一个是体积。
二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。
模型：
11
1
max .
,1,2,3...n
i i
i n
i i i
n
i i i
i c x st a x a b x b
x z i n
===≤≤∈=∑∑∑
例题
码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表:
现求如何装载这四种货物使价值量最大。
1
1
1
max
.,1,2,3...n
i i i
n
i i i
n
i i i
i c x st a x a b x b
x z i n
===≤≤∈=∑∑∑
可用动态规划来解决
1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量，
2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段）
3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。
状态转移方程：
11k k k k k k k k
S S a x R R b x ++=-=-
()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装
入前j 中货品的价值。（j=1,2,3,4）
二维指派问题
问题描述
设有K 批货物需要从A 地运输到N 地, 途经B 地换装，A 地可用车辆有I 辆，B 地可用车辆为J 辆。每辆车一次只能运输一批货物, 同一车辆运输不同批次的货物费用不同。如果I, J, K 中有两个或者两个以上不相等, 如何优化车辆与货物的搭配, 使运输费用最小。此问题是一个二维不平衡指派问题，假设I ≤J 。
以yi 和uj 分别代表A 地车辆i 和B 地车辆j 运输的货物批数, yi 和uj 的表达式为:
以i A 表示A 地的第i 辆车, j B 表示B 地的第j 辆车, k 表示第k 项任务( 即第k 批货物) , 定义三维0- 1变量ijk X , 如果i A 与j B 组合运输第k 批货物, 则ijk X =1 否则, ijk X =0。i A 与j B 运输第k 批货物的费用为c ijk 以费用C 最小为目标, 模型如下:
111
11
11
11
1
1
Min ,1,2,,,(2),1,2,,,(3)1,1,2,
,,(4)
,(5)
I
J
K
ijk ijk
i j k
J
K
ijk
i j k
I K
ijk j i k
I J
ijk i j
I
J
i j
i
j
C C X X y i I X u j J X k K y u K ============
=======
=∑∑∑∑∑∑∑∑∑∑∑ 式( 2) 表示车辆Ai 运输货物批数为yi,
式( 3) 表示车辆Bj 运输货物批数为uj,
式( 4) 表示每批货物必须且只能由A 地某一车辆和B 地某一车辆共同运输, 式( 5) 表示A 地车辆和B 地车辆运输货物的总批数为K 。
车间作业调度问题（JSP ） 问题描述：
JSP 问题描述：
n 个加工顺序和时间不同的工件在m 台机器上加工，每个工件包含m 道工序，且每道工序使用某台机器的时间已知，调度的任务是确定各机器上所有工件的加工次序，约束条件被满足的同时以使总加工时间最优。对应的己知条件如下所述: 1) 加工的机器集M=(123,,,...,m
m m m m ),其中
i
m 表示第i 个加工的机器， 2）加工的工件集O=(
123,,,...,n
o o o o ),其中，
i
o 表示第i 个加工的工件
3）各工件的工序集合J=(
123,,,...,n
J J J J ),其中，
i 123(j ,j ,j ...j ...j )
i i i ik im J =
第i 个工件的第k 道工序用j ik
表示，(i=1,2,..n; j=1,2,…m)
4)工件各工序的加工时间123n (,,......)k T T T T T T =，
123(,,......)
i i i i ik im T t t t t t =，
其中
ik
t 表示第i 个工件的第k 道工序需要的加工时间
作业车间调度需要考虑如下约束:
Cons1：每道工序在指定的机器上加工，且必须在其前一道工序加工完成后才能开始加工；
Cons2：某一时刻1台机器只能加工1个作业； Cons3：每个作业只能在1台机器上加工1次；
Cons4：各作业的工序顺序和加工时间已知，不随加工排序的改变而改变。
根据上述条件，构造构建了工序排列矩阵J 、加工时间矩阵T 和各机器对应加工工序的调度矩阵
J M
因此，所有调度方案均应满足如下的约束条件的数学表达式:
1）(1)1,,1,,，++≤==ij ij i j S t S i n j m
其中，
ij
S 为工件i 的第j 道工序的起始加工时间。
ij
t 表示工件i 的第j 道工序加工所需时间
(1)
+i j S 为工件i 的第j+1 道工序的起始加工时间
表明必须进行完上一步加工后才能进行下一步加工
2）
max max i 11ikh i ikh i ik ;,1,,;1,,;,1,
,;1,
,min()min (),,s.t
(1)(1)0,,0,1,
max max ααα≤≤≤≤+≤==+≤==??????
==+?∈∈????
??????
+≤+-+≤+-≥=ijk ij ghk ijk ij ghk ij ij j i n j m ik ik ih ik ik jk jk ik jk S t S i g n h m S t S i g n h m
C C c t J J M M c t c M c t c M x c x h ijk 1i 0,1,i j k x 0,，工件在机器k 上加工早于机器h 否则
工件早于工件在机器上加工否则
?=?
??=?
?
ijk
S 表示工件i 的第j 道工序在机器k 上的起始加工时刻
ij
t 表示工件i 的第j 道工序加工所需时间
ghk
S 表示工件g 的第h 道工序在机器k 上的起始加工时刻
表明机器只有在上一道工序加工完成后才能进行下一道工序加工。
对于一个具体的车间作来调度问题，结合已知约束条件和各工序的加工时间，可以计算出各机器完成所有工件所需要的时间。将最短加工时间作为车间作业高度优化目标，那么车间作业调度问题优化目标函数可以定义为:
()()()min max =J E F M T
举例:
下面给出作业车间调度问题的一个实例，其中每个工序上标注有一对数值（m,p ），其中，m 表示当前工序必须在第m 台机器上进行加工，p 表示第m 台机器加工当前工序所需要的加工时间。（注：机器和作业的编号从0开始） job0=[(0,3),(1,2),(2,2)] job1=[(0,2),(2,1),(1,4)] job2=[(1,4),(2,3)]
在这个例子中，作业job0有3道工序：它的第1道工序上标注有(0,3)，其表示第1道工序必须在第0台机器上进行加工，且需要3个单位的加工时间；它的第2道工序上标注有(1,2)，其表示第2道工序必须在第1台机器上进行加工，且需要2个单位的加工时间；余下的同理。总的来说，这个实例中共有8道工序。
该问题的一个可行解是L=8道工序开始时间的一个排列，且满足问题的约束。下图给出了一个可行解的示例：
(完整版)智能算法在柔性车间调度中的应用
智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。 关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言 柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度 问题的扩展，是实际生产中迫切需要解决的一类问 题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。 作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。 图1 三个工件两台机器的JSP问题 为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对 值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。 这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。 另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。 参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。
柔性工作车间调度问题的多目标优化方法研究
第15卷第8期计算机集成制造系统 Vol.15No.82009年8月 Computer Integrated Manufacturing Systems Aug.2009 文章编号:1006-5911(2009)08-1592-07 收稿日期:2008207208;修订日期:2008209201。Received 08J uly 2008;accepted 01Sep.2008. 基金项目:国家863/CIMS 主题资助项目(2007AA04Z190,2008AA042301);国家自然科学基金资助项目(50835008,50875237)。Found ation i 2 tems :Project supported by t he National High 2Tech.R &D Program for CIMS ,China (No.2007AA04Z190,2008AA042301),and t he National Natural Science Foundation ,China (No.50835008,50875237). 作者简介:魏 巍(1982-),男,辽宁沈阳人,浙江大学CAD &CG 国家重点实验室博士研究生,主要从事产品配置优化、产品信息建模、多目标 优化和先进制造技术等研究。E 2mail :boyweiwei @https://www.wendangku.net/doc/088059514.html, ;+通信作者E 2mail :fyxtv @https://www.wendangku.net/doc/088059514.html, 。 柔性工作车间调度问题的多目标优化方法研究 魏 巍1,谭建荣1,冯毅雄+1,张 蕊2 (1.浙江大学流体传动及控制国家重点实验室,浙江 杭州 310027; 2.华晨金杯汽车有限公司,辽宁 沈阳 110044) 摘 要:针对各工件目标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多目标优化数学模型。针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto 进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto 综合最优解。最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题。 关键词:柔性车间调度;多目标优化;遗传算法;强度Pareto 进化算法中图分类号:TP278 文献标识码:A Multi 2objective optimization method research on flexible job shop scheduling problem W EI Wei 1 ,TA N J ian 2rong 1 ,F EN G Yi 2x iong +1 ,Z HA N G Rui 2 (1.State K ey Laboratory of Fluid Power T ransmission &C ontrol ,Zhejiang University ,Hangzhou 310027,China ; 2.Shenyang Brilliance J INB EI Automotive Corporation Limited.,Shenyang 110044,China ) Abstract :To solve the multi 2objective optimization problem in flexible job shop scheduling ,the multi 2objective sched 2uling optimization model ,namely the cost 、quality and term ,was constructed.While the traditional genetic algo 2rithm which combined random weigh could not solve the multi 2objective scheduling optimization problem commend 2ably.An improved strength Pareto evolutionary algorithm was employed to optimize the multi 2objective optimization model parallelly.As a result ,the optimal schema of flexible job shop scheduling was presented in the form of Pareto optimal sets.At last ,an instance related with the project in the air separation equip industry was given to prove that the proposed method could solve multi 2objective optimization problem in flexible job shop scheduling effectively.K ey w ords :flexible job shop scheduling ;multi 2objective optimization ;genetic algorithm ;SPEA2 0 引言 柔性作业车间调度问题(Flexible Job Shop Scheduling Problem ,FJ SP )是指带有机器可选柔性的车间调度问题。相对经典作业车间调度问题,FJ SP 突破了资源唯一性限制,每个工序可由多个不 同的机器完成,更加符合实际的生产环境。因此,研 究FJ SP 具有重要的理论价值和应用意义。 在处理FJ SP 问题上,文献[1]提出分布法,其基本思想是将机器分配问题和调度问题分开考虑,以降低FJ SP 问题的复杂性。文献[2]～文献[4]分别采用贪婪法、模拟退火算法和禁忌搜索法对FJ SP 问题进行优化求解。文献[5]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标
最新数学建模习题答案资料
数学建模部分课后习题解答 中国地质大学 能源学院 华文静 1.在稳定的椅子问题中，如设椅子的四脚连线呈长方形，结论如何？ 解： 模型假设 （1） 椅子四条腿一样长，椅脚与地面接触处视为一点，四脚的连线呈长方形 （2） 地面高度是连续变化的，沿任何方向都不会出现间断（没有像台阶那样的情况）， 即从数学角度来看，地面是连续曲面。这个假设相当于给出了椅子能放稳的必要条件 （3） 椅子在任何位置至少有三只脚同时着地。为了保证这一点，要求对于椅脚的间 距和椅腿的长度而言，地面是相对平坦的。因为在地面上椅脚间距和椅腿长度的尺寸大小相当的范围内，如果出现深沟或凸峰（即使是连续变化的），此时三只脚是无法同时着地的。 模型建立 在上述假设下，解决问题的关键在于选择合适的变量，把椅子四只脚同时着地表示出来。首先，引入合适的变量来表示椅子位置的挪动。生活经验告诉我们，要把椅子通过挪动放稳，通常有拖动或转动椅子两种办法，也就是数学上所说的平移与旋转变换。然而，平移椅子后问题的条件没有发生本质变化，所以用平移的办法是不能解决问题的。于是可尝试将椅子就地旋转，并试图在旋转过程中找到一种椅子能放稳的情形。 注意到椅脚连线呈长方形，长方形是中心对称图形，绕它的对称中心旋转180度后，椅子仍在原地。把长方形绕它的对称中心旋转，这可以表示椅子位置的改变。于是，旋转角度θ这一变量就表示了椅子的位置。为此，在平面上建立直角坐标系来解决问题。 设椅脚连线为长方形ABCD,以对角线AC 所在的直线为x 轴，对称中心O 为原点，建立平面直角坐标系。椅子绕O 点沿逆时针方向旋转角度θ后，长方形ABCD 转至A1B1C1D1的位置，这样就可以用旋转角）0（πθθ≤≤表示出椅子绕点O 旋转θ后的位置。 其次，把椅脚是否着地用数学形式表示出来。当椅脚与地面的竖直距离为零时，椅脚就着地了，而当这个距离大于零时，椅脚不着地。由于椅子在不同的位置是θ的函数，因此，椅脚与地面的竖直距离也是θ的函数。 由于椅子有四只脚，因而椅脚与地面的竖直距离有四个，它们都是θ的函数，而由假设（3）可知，椅子在任何位置至少有三只脚同时着地，即这四个函数对于任意的θ，其函数值至少有三个同时为0。因此，只需引入两个距离函数即可。考虑到长方形ABCD 是对称中心图形，绕其对称中心O 沿逆时针方向旋转180度后，长方形位置不变，但A,C 和B,D 对换了。因此，记A ，B 两脚与地面竖直距离之和为)(θf ，C,D 两脚之和为 )(θg ，其中[]πθ，0∈，使得)()(00θθg f =成立。 模型求解 如果0)0()0(== g f ，那么结论成立。
流水车间调度问题的研究-周杭超
流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品
混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==L L 。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。
数学建模作业——实验1
数学建模作业——实验1 学院：软件学院 姓名： 学号： 班级：软件工程2015级 GCT班 邮箱： 电话： 日期：2016年5月10日
基本实验 1.椅子放平问题 依照1.2.1节中的“椅子问题”的方法，将假设中的“四腿长相同并且四脚连线呈正方形”，改为“四腿长相同并且四脚连线呈长方形”，其余假设不变，问椅子还能放平吗？如果能，请证明；如果不能，请举出相应的例子。 答：能放平，证明如下： 如上图，以椅子的中心点建立坐标，O为原点，A、B、C、D为椅子四脚的初始位置，通过旋转椅子到A’、B’、C’、D’，旋转的角度为α，记A、B两脚，C、D两脚距离地面的距离为f(α)和g(α)，由于椅子的四脚在任何位置至少有3脚着地，且f(α)、g(α)是α的连续函数，则f(α)和g(α)至少有一个的值为0，即f(α)g(α)=0，f(α)≥ 0，g(α)≥0，若f(0)＞0，g(0)=0，
则一定存在α’∈（0，π），使得 f(α’)=g(α’)=0 令α=π（即椅子旋转180°,AB 边与CD 边互换），则 f(π)=0，g(π)＞0 定义h(α)=f(α)-g(α)，得到 h(0)=f(0)-g(0)＞0 h(π)=f(π)-g(π)＜0 根据连续函数的零点定理，则存在α’∈（0，π），使得 h(α’)=f(α’)-g(α’)=0 结合条件f(α’)g(α’)=0,从而得到 f(α’)=g(α’)=0，即四脚着地，椅子放平。 2. 过河问题 依照1.2.2节中的“商人安全过河”的方法，完成下面的智力游戏：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米之一，而当人不在场时，猫要吃鸡、鸡要吃米，试设计一个安全过河的方案，并使渡河的次数尽量的少。 答：用i =1,2,3,4分别代表人，猫，鸡，米。1=i x 在此岸，0=i x 在对岸，()4321,,,x x x x s =此岸状态，()43211,1,1,1x x x x D ----=对岸状态。安全状态集合为 :
数学建模习题集及标准答案
第一部分课后习题 1.学校共1000名学生，235人住在A宿舍，333人住在B宿舍，432人住在C宿舍。学 生们要组织一个10人的委员会，试用下列办法分配各宿舍的委员数： （1）按比例分配取整数的名额后，剩下的名额按惯例分给小数部分较大者。 （2）2.1节中的Q值方法。 （3）d’Hondt方法：将A，B，C各宿舍的人数用正整数n=1，2，3，…相除，其商数如下表： 将所得商数从大到小取前10个（10为席位数），在数字下标以横线，表中A，B，C行有横线的数分别为2，3，5，这就是3个宿舍分配的席位。你能解释这种方法的道理吗。 如果委员会从10人增至15人，用以上3种方法再分配名额。将3种方法两次分配的结果列表比较。 （4）你能提出其他的方法吗。用你的方法分配上面的名额。 2.在超市购物时你注意到大包装商品比小包装商品便宜这种现象了吗。比如洁银牙膏50g 装的每支1.50元，120g装的3.00元，二者单位重量的价格比是1.2：1。试用比例方法构造模型解释这个现象。 （1）分析商品价格C与商品重量w的关系。价格由生产成本、包装成本和其他成本等决定，这些成本中有的与重量w成正比，有的与表面积成正比，还有与w无关的因素。 （2）给出单位重量价格c与w的关系，画出它的简图，说明w越大c越小，但是随着w的增加c减少的程度变小。解释实际意义是什么。 3.一垂钓俱乐部鼓励垂钓者将调上的鱼放生，打算按照放生的鱼的重量给予奖励，俱乐部 只准备了一把软尺用于测量，请你设计按照测量的长度估计鱼的重量的方法。假定鱼池中只有一种鲈鱼，并且得到8条鱼的如下数据（胸围指鱼身的最大周长）： 先用机理分析建立模型，再用数据确定参数 4.用宽w的布条缠绕直径d的圆形管道，要求布条不重叠，问布条与管道轴线的夹角 应 多大（如图）。若知道管道长度，需用多长布条（可考虑两端的影响）。如果管道是其他形状呢。
置换流水车间调度问题的MATLAB求解
物流运筹实务课程设计 题目：置换流水车间调度问题的MATLAB求解置换流水车间调度问题的MATLAB求解
目录 一、前言 (5) 二、问题描述 (6) 三、算法设计 (7) 四、实验结果 (15)
摘要 自从Johnson 1954年发表第一篇关于流水车间调度问题的文章以来．流水车间调度问题引起了许多学者的关注。安排合理有效的生产调度是生产活动能井然有序开展，生产资源得到最佳配置，运作过程简明流畅的有力保证。流水车间调度问题是许多实际流水线生产调度问题的简化模型。它无论是在离散制造工业还是在流程工业中都具有广泛的应用。因此，对进行研究具有重要的理论意义和工程价值。流水线调度问题中一个非常典型的问题，而置换流水线调度问题作为FSP问题的子问题，是一个著名的组合优化问题。该问题是一个典型的NP难问题，也是生产管理的核心内容。随着生产规模的扩大，流水线调度问题的优化对提高资源利用率的作用越来越大，因此对其研究具有重要的
理论和现实意义。 关键字：流水车间，单件小批量生产，jsp模型，Matlab 前言 企业资源的合理配置和优化利用很大程度上体现在车间一层的生产活动中,所以加强车间层的生产计划与控制一直在企业生产经营活动中占有十分重要的地位。车间生产计划与控制的核心理论是调度理论。车间调度问题是一类重要的组合优化问题。为适应订货式、多品种、小批量生产的需要,引进了置换流水车间调度概念。在置换流水车间调度优化后,可以避免或大大减少流程工作时间、提高生产效率。因此,研究成组技术下车间调度问题是很有必要的。生产调度，即对生产过程进行作业计划，是整个个先进生产制造系统实现管理技术、优化技术、白动化与计算机技术发展的核心。置换流水车间调度问题是许多实际生产调度问题的简化模型。生产计划与调度直接关系着企业的产出效率和生产成本，有效的计划与调度算法能最大限度地提高企业的效益。调度问题是组合优化问题，属于NP问题，难以用常规力一法求解。随着制造业的快速发展，大规模定制生产、全球化制造等思想的提出，使车间调度问题呈现出以下的新特点:约束条件多，时间复杂度高，空问复杂度高。这将导致在许多情况下，求解所建立的数学模型的快速性无法满
数学模型数学建模 第二次作业 微分方程实验
2 微分方程实验 1、微分方程稳定性分析 绘出下列自治系统相应的轨线，并标出随t 增加的运动方向，确定平衡点，并按稳定的、渐近稳定的、或不稳定的进行分类： ,,,+1,(1)(2)(3)(4);2;2;2.dx dx dx dx x x y x dt dt dt dt dy dy dy dy y y x y dt dt dt dt ????==-==-????????????????===-=-???????? 解：（1）根据定义，代数方程组的实根即为系统的平衡点，即P(0, 0)， 利用直接法判断其稳定性。在点P(0,0)处，系统的线性近似方程的系数矩阵为 1001A ??=?? ?? ，解得其特征值λ1=1，λ2=1； p=-(λ1+λ2)=-2<0，q=λ1λ2=1>0；对照稳定性的情况表，可知平衡点(0, 0)是不稳定的。 图形如下： （2）根据定义，代数方程组的实根即为系统的平衡点，即P(0, 0)， 利用直接法判断其稳定性。解得其特征值λ1=-1，λ2=2； p=-(λ1+λ2)=-1<0，q=λ1λ2=-2<0；易知平衡点(0, 0)是不稳定的。
（3）根据定义，代数方程组的实根即为系统的平衡点，即P(0, 0)， 利用直接法判断其稳定性。解得其特征值λ1=0 + 1.4142i，λ2=0 - 1.4142i；p=-(λ1+λ2)=0，q=λ1λ2=1.4142；易知平衡点(0, 0)是不稳定的。 （4）根据定义，代数方程组的实根即为系统的平衡点，即P(1, 0)， 利用直接法判断其稳定性。解得其特征值λ1=-1，λ2=-2； p=-(λ1+λ2)=3，q=λ1λ2=2；易知平衡点(1, 0)是稳定的。
基于文化遗传算法求解柔性作业车间调度问题
第16卷第4期计算机集成制造系统 Vol.16No.42010年4月 Computer Integrated Manufacturing Systems Apr.2010 文章编号:1006-5911(2010)04-0861-06 收稿日期:2009204220;修订日期:2009209216。Received 20Apr.2009;accepted 16Sep.2009. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Found ation item :Project supported by t he National Natural Science Foundation , China (No.70771008,70371057). 作者简介:李铁克(1958-),男,吉林长春人,北京科技大学经济管理学院教授,博士生导师,主要从事先进制造管理、生产计划与调度、智能算 法等的研究。E 2mail :tiekeli @https://www.wendangku.net/doc/088059514.html, 。 基于文化遗传算法求解柔性作业车间调度问题 李铁克,王伟玲,张文学 (北京科技大学经济管理学院,北京 100083) 摘 要:在分析柔性作业车间调度问题特性的基础上,提出了一种采用主群体空间和信仰空间的双层进化结构的调度算法。该算法采用优良调度方案的知识信息构成信仰空间;提出一种二维矩阵的集成编码;基于工序顺序编码和基于机器分配编码的两种交叉和变异算子在主群体空间进行传统的遗传操作;通过具有自学习特点的相似性选择算子,使子代更好地继承父代的优良特征。通过典型算例的计算实验,表明算法在计算效率和求解质量上均具有较好的效果。 关键词:柔性作业车间调度;文化算法;遗传算法;选择算子中图分类号:TP301.6 文献标志码:A Solving flexible Job Shop scheduling problem based on cultural genetic algorithm L I Tie 2ke ,W A N G Wei 2ling ,Z HA N G Wen 2x ue (School of Economics &Management ,University of Science &Technology Beijing ,Beijing 100083,China )Abstract :Based on the analysis of the characteristics of Flexible Job Shop Scheduling (FJ SP )problem ,the double 2layer evolution scheduling algorithm with f rame population space and belief space to solve FJ SP was proposed.This algorithm adopted usef ul knowledge of excellent scheduling schemes to form belief space.A two 2dimensional matrix integrated coding was put forward.Traditional genetic operations were conducted in f rame population space among two effective crossover operators and mutation operators ,which were designed on the basis of the integration of ma 2chine assignment and operation sequence for the genetic algorithm.By selection operators with similar self 2learning char 2acteristics ,son 2generations inherited excellent characteristics from parent 2generations.Experimental results indicated that the proposed algorithm outperformed the current approaches in computation efficiency and solution quality.K ey w ords :flexible Job Shop scheduling ;cultural algorithm ;genetic algorithm ;selection operator 0 引言 柔性作业车间调度问题(Flexible Job 2shop Scheduling Problem ,FJ SP )是经典作业车间调度问题(Job 2shop Scheduling Problem ,J SP )的扩展[1]。在J SP 中,仅考虑工件具有唯一确定的加工工艺路线的情况。而在FJ SP 中,每道工序可以在多台机器上加工,工件具有可选择的加工路线,并且在不同机器上加工所需的时间不同,因此FJ SP 比J SP 更 接近实际制造环境,是实际生产中亟需解决的一类调度问题。 FJ SP 不仅需要确定工件的加工顺序,还要确定某道工序由哪台机器加工。因此,FJ SP 是比J SP 更为复杂的N P 2hard 问题,一般不存在有效的多项式算法[2]。现有的研究方法主要分为精确算法、启发式规则[3]和元启发式算法(如模拟退火、遗传算法(Genetic Algorit hm ,GA )等)[4]。其中精确算法无法对大规模FJ SP 进行有效求解;启发式规则求解
西南大学2016年春《数学建模》作业及答案(已整理)(共5次)
西南大学2014年春《数学建模》作业及答案(已整理) 第一次作业 1：[填空题] 名词解释: 1．原型 2．模型 3．数学模型 4．机理分析 5．测试分析 6．理想方法 7．计算机模拟 8．蛛网模型 9．群体决策 10．直觉 11．灵感 12．想象力 13．洞察力 14．类比法 15．思维模型 16．符号模型 17．直观模型 18．物理模型19．2倍周期收敛20．灵敏度分析21．TSP问题22．随机存储策略23．随机模型24．概率模型25．混合整数规划26．灰色预测 参考答案： 1．原型：原型指人们在现实世界里关心、研究或者从事生产、管理的实际对象。2．模型：指为某个特定目的将原形的某一部分信息简缩、提炼而构造的原型替代物。3．数学模型：是由数字、字母或其它数字符号组成的，描述现实对象数量规律的数学公式、图形或算法。4．机理分析：根据对客观事物特性的认识，找出反映内部机理的数量规律，建立的模型常有明显的物理意义或现实意义。5．测试分析：将研究对象看作一个"黑箱”系统，通过对系统输入、输出数据的测量和统计分析，按照一定的准则找出与数据拟合得最好的模型。6．理想方法：是从观察和经验中通过想象和逻辑思维，把对象简化、纯化，使其升华到理状态，以其更本质地揭示对象的固有规律。7．计算机模拟：根据实际系统或过程的特性，按照一定的数学规律用计算机程序语言模拟实际运行情况，并依据大量模拟结构对系统或过程进行定量分析。8．蛛网模型：用需求曲线和供应曲线分析市场经济稳定性的图示法在经济学中称为蛛网模型。9．群体决策：根据若干人对某些对象的决策结果，综合出这个群体的决策结果的过程称为群体决策。10．直觉：直觉是人们对新事物本质的极敏锐的领悟、理解或推断。11．灵感：灵感是指在人有意识或下意识思考过程中迸发出来的猜测、思路或判断。12．想象力：指人们在原有知识基础上，将新感知的形象与记忆中的形象相互比较、重新组合、加工、处理，创造出新形象，是一种形象思维活动。13．洞察力：指人们在充分占有资料的基础上，经过初步分析能迅速抓住主要矛盾，舍弃次要因素，简化问题的层次，对可以用那些方法解决面临的问题，以及不同方法的优劣作出判断。14．类比法：类比法注意到研究对象与以熟悉的另一对象具有某些共性，比较二者相似之处以获得对研究对象的新认识。15．思维模型：指人们对原形的反复认识，将获取的知识以经验的形式直接储存于人脑中，从而可以根据思维或直觉作出相应的决策。16．符号模型：是在一定约束条件或假设下借助于专门的符号、线条等，按一定形式组合起来描述原型。17．直观模型：指那些供展览用的实物模型以及玩具、照片等，通常是把原型的尺寸按比例缩小或放大，主要追求外观上的逼真。18．物理模型：主要指科技工作者为一定的目的根据相似原理构造的模型，它不仅可以显示原型的外形或某些特征，而且可以用来进行模拟实验，间接地研究原型的某些规律。19．2倍周期收敛：在离散模型中，如果一个数列存在两个收敛子列就称为2倍周期收敛。20．灵敏度分析：系数的每个变化都会改变线性规划问题，随之也会影响原来求得的最优解。为制定一个应付各种偶然情况的全能方法，必须研究以求得的最优解是怎样随输入系数的变化而变化的。这叫灵敏性分析。21．TSP问题：在加权图中寻求最佳推销员回路的问题可以转化为在一个完备加权图中寻求最佳哈密顿圈的问题，称为TSP问题。22．随机存储策略：商店在订购货物时采用的一种简单的策略，是制定一个下界s和一个上界S，当周末存货不小于s时就不定货；当存货少于s 时就订货，且定货量使得下周初的存量达到S，这种策略称为随机存储策略。23．随机模型：如果随机因素对研究对象的影响必须考虑，就应该建立随机性的数学模型，简称为随机模型。24．概
数学建模第二次作业(3)
数学建模 任意两个城市之间的最廉价路线 参与人员信息： 2012年 6 月 6 日
一、问题提出 某公司在六个城市C1、C2、C3、C4、C5、C6中都有分公司，从Ci 到Cj 的直达航班票价由下述矩阵的第i 行、第j 列元素给出（∞表示无直达航班），该公司想算出一张任意两个城市之间最廉价路线表，试做出这样的表来。 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 二 、问题分析 若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通 常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。 题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。（此两点为主要约束条件） Floyd 算法，具体原理如下： （1） 我们确定本题为全局最短路问题，并采用求距离矩阵的方法 根据路线及票价表建立带权矩阵W ，并把带权邻接矩阵我w 作为距离矩阵的初始值，即(0)(0)()ij v v D d W ?== （2）求路径矩阵的方法 在建立距离矩阵的同时可建立路径矩阵R ，()ij v v R r ?=，ij r 的含义是从i v 到j v 的最短路径要经过点号为ij r 的点。 （3）查找最短路径的方法 若()1v ij r p =，则点1p 是点i 到j 的最短距离的中间点，然后用同样的方法再分头查找。 三、 模型假设： 1.各城市间的飞机线路固定不变 2.各城市间飞机线路的票价不改变 3.忽略乘客除票价以外的各项开销费用 4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。
基于深度强化学习的柔性车间调度问题现代研究
基于深度强化学习的柔性车间调度问题现代研究 摘要本文针对多目标柔性作业车间调度问题进行研究，分别以机器总负荷和设备利用率为性能指标，建立了多目标柔性作业车间调度模型。由于传统的企业调度算法忽略了历史数据的价值，在实时事件发生后不能快速响应支持，同时为了迎合“智慧工厂”的趋势，提出了一种适用于柔性作业车间调度的深度强化学习方法，实现了从状态输入到行为输出的直接控制。最后，通过实验案例验证了该方法在解决多目标柔性作业车间调度问题的可行性和有效性。 关键词柔性作业车间调度；深度强化学习；状态编码；多智能体 前言 近年来，市场中定制化服务已经成为一种普遍需求，“随需应变”的理念得到了企业管理者的高度重视。柔性生产是指通过先进制造设备来实现多品种、小批量的生产方式，其主要优点是增强了制造企业的灵活性和应变能力，提高了设备利用率。柔性作业车间调度问题（Flexible job-shop problem，FJSP）是传统作业车间调度问题的重要扩展，是目前车间调度问题的研究热点。 与传统的作业车间调度问题相比，柔性作业车间调度问题减少了机器能力约束，是更为复杂的NP-hard问题。目前的相关研究主要集中在算法效率改进[1-3]、问题实际化[4-7]、优化目标扩展[8-10]三个方面。在柔性作业车间调度问题上一般采用两种方法求解：启发式方法和集成方法[11]。问题实际化的研究主要通过加入更多生产相关约束，使得问题模型更加贴近实际生产。许多学者在上述三个方面进行了深入的研究，但是他们对于企業过去的生产调度历史数据并没有进行关注，忽略了其价值。 随着“中国制造2025”的提出，智能制造成为推进该项战略的重要举措。智能制造包括了智能制造技术和智能制造系统。深度强化学习作为一种端对端的感知与控制系统，为构建智能化的生产调度系统提供了重要指导和有效支持。 本文针对柔性作业车间调度问题，以最小化机器总负荷和最大化设备利用率为目标。通过对生产状态的编码，将每个工件构建为一个智能体。采用多智能体Actor-Critic算法，使得工件智能体学习彼此协作，为求解多目标柔性作业车间调度问题提供一种智能化的方法。 1 多目标柔性作业车间优化建模 1.1 问题描述 nm的FJSP问题可以描述为：一个拥有m台机器的加工系统，加工处理n 个工件。其中每个工件包含一道或者多道工序，每道工序可以在一台或者多台机器上进行加工处理，且相对应的加工时间取决于所分配的机器能力。对于该类问
数学建模题目及答案
09级数模试题 1. 把四只脚的连线呈长方形的椅子往不平的地面上一放，通常只有三只脚着地，放不稳，然后稍微挪动几次，就可以使四只脚同时着地，放稳了。试作合理的假设并建立数学模型说明这个现象。（15分） 解：对于此题，如果不用任何假设很难证明，结果很 可能是否定的。 因此对这个问题我们假设： （1）地面为连续曲面 （2）长方形桌的四条腿长度相同 （3）相对于地面的弯曲程度而言，方桌的腿是足够长的 （4）方桌的腿只要有一点接触地面就算着地。 那么，总可以让桌子的三条腿是同时接触到地面。 现在，我们来证明：如果上述假设 条件成立，那么答案是肯定的。以长方 桌的中心为坐标原点作直角坐标系如图 所示，方桌的四条腿分别在A、B、C、D 处，A、、D的初始位置在与x轴平行，再 假设有一条在x轴上的线,则也与A、B，C、D平行。当方桌绕中心0旋转时，对角线与x轴的夹角记为θ。 容易看出，当四条腿尚未全部着地时，腿到地面的距离是不确定的。为消除这一不确定性，令() fθ为A、B离地距离之和，
()g θ为C 、D 离地距离之和，它们的值由θ唯一确定。由假设（1）， ()f θ,()g θ均为θ的连续函数。又由假设（3） ，三条腿总能同时着地， 故()f θ()g θ=0必成立（?θ）。不妨设(0)0f =(0)0g >（若(0)g 也为0，则初始时刻已四条腿着地，不必再旋转），于是问题归结为： 已知()f θ,()g θ均为θ的连续函数，(0)0f =,(0)0g >且对任意θ有00()()0f g θθ=，求证存在某一0θ，使00()()0f g θθ=。 证明：当θ=π时，与互换位置，故()0f π>，()0g π=。作()()()h f g θθθ=-，显然，()h θ也是θ的连续函数，(0)(0)(0)0h f g =-<而()()()0h f g πππ=->，由连续函数的取零值定理，存在0θ，00θπ<<，使得0()0h θ=，即00()()f g θθ=。又由于00()()0f g θθ=，故必有00()()0f g θθ==，证毕。 2.学校共1000名学生，235人住在A 宿舍，333人住在B 宿舍，432人住在C 宿舍。学生 们要组织一个10人的委员会，试用合理的方法分配各宿舍的委员数。（15分） 解：按各宿舍人数占总人数的比列分配各宿舍的委员数。设：A 宿舍的委员数为x 人，B 宿舍的委员数为y 人，C 宿舍的委员数为z 人。计算出人数小数点后面的小数部分最大的整数进1，其余取整数部分。 则 10； 10=235/1000；
初等数学建模试题极其标准答案
1.你要在雨中从一处沿直线走到另一处，雨速是常数，方向不变。 你是否走得越快，淋雨量越少呢？ 2.假设在一所大学中，一位普通教授以每天一本的速度开始从图书 馆借出书。再设图书馆平均一周收回借出书的1/10，若在充分长的时间内，一位普通教授大约借出多少年本书？ 3.一人早上6：00从山脚A上山，晚18：00到山顶B；第二天，早 6：00从B下山，晚18：00到A。问是否有一个时刻t,这两天都在这一时刻到达同一地点？ 4.如何将一个不规则的蛋糕I平均分成两部分？ 5.兄妹二人沿某街分别在离家3公里与2公里处同向散步回家，家 中的狗一直在二人之间来回奔跑。已知哥哥的速度为3公里/小时，妹妹的速度为2公里/小时，狗的速度为5公里/小时。分析半小时后，狗在何处？ 6.甲乙两人约定中午12：00至13：00在市中心某地见面，并事先 约定先到者在那等待10分钟，若另一个人十分钟内没有到达，先到者将离去。用图解法计算，甲乙两人见面的可能性有多大？ 7.设有n个人参加某一宴会，已知没有人认识所有的人，证明：至 少存在两人他们认识的人一样多。 8.一角度为60度的圆锥形漏斗装着10 端小孔的 面积为0.5 9.假设在一个刹车交叉口，所有车辆都是由东驶上一个1/100的斜
坡，计算这种情 下的刹车距离。如果汽车由西驶来，刹车距离又是多少？ 10. 水管或煤气管经常需要从外部包扎以便对管道起保护作用。包扎时用很长的带子缠绕在管道外部。为了节省材料，如何进行包扎才能使带子全部包住管道而且带子也没有发生重叠。 :顶=1：a:b ，选坐v>0,而设语雨速 L( 1q -+v x ),v≤x Q(v)= L( v x -q +1),v>x 2.解：由于教授每天借一本书，即一周借七本书，而图书馆平均每周
流水车间调度问题的研究-周杭超
流水车间调度问题的研究-周杭超
流水车间调度问题的研究 机械工程学院 2111302120 周杭超 如今，为了满足客户多样化与个性化的需求，多品种、小批量生产己经为一种重要的生产方式。与过去大批量、单一的生产方式相比，多品种、小批量生产可以快速响应市场，满足不同客户的不同需求，因此，受到越来越多的企业管理者的重视。特别是以流水线生产为主要作业方式的企业，企业管理者致力于研究如何使得生产均衡化，以实现生产批次的最小化，这样可以在不同批次生产不同品种的产品。在这种环境下，对于不同批次的产品生产进行合理调度排序就显得十分重要。 在传统的生产方式中，企业生产者总是力求通过增加批量来减小设备的转换次数，因此在生产不同种类的产品时，以产品的顺序逐次生产或用多条生产线同时生产。这样，必然会一次大批量生产同一产品，很容易造成库存的积压。在实际生产中如果需要生产A, B, C, D 四种产品各100件，各种产品的节拍都是1分钟，如果按照传统的做法，先生产出100件A产品，其次是B，然后是C，最后生产产品D。在这种情况下，这四种产品的总循环时间是400分钟。然而，假设客户要求的循环时间为200分钟(四种产品的需求量为50件)，那么在200分钟的时间内就只能生产出产品A和产品B，因而不能满足客户需求，同时还会过量生产产品A和B，造成库存积压的浪费。这种生产就是非均衡的，如图1所示。 比较均衡的生产方式(图2 )是:在一条流水线上同时将四种产品
混在一起生产，并且确定每种品种一次生产的批量。当然，如果在混合生产时不需要对设备进行转换，那么单件流的生产方式是最好的。然而，在实际生产A, B, C ， D 四种不同产品时，往往需要对流水线上的某些设备进行工装转换。单件流的生产方式在此难以实现，需要根据换装时间来确定每种产品一次生产的批量。同时，由于现实生产中不同产品在流水线上各台机器的加工时间很难相同，因此，流水线的瓶颈会随着产品组合的不同而发生变化。当同一流水线加工多产品，并且每种产品在各道工序(各台机器)的加工时间差异较大时，瓶颈就会在各道工序中发生变化，如何对各种产品的投产顺序进行优化以协调这些变化的瓶颈是生产管理中一个很重要的问题。 图1 图2 因而对流水线调度问题的研究正是迎合这种多品种、小批量生产方式的需要，我们要讨论得是如何对流水线上生产的不同产品的调度顺序进行优要化。 流水车间调度问题一般可以描述为n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为(1,,;1,,)ij t i n j m ==。问题的目标是确定个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。