单机调度中平均流程时间和延期工件数的双目标问题

1 引言 本文在具有平均流程时间和延期工件数两个目标的情况下对单机多目标问题进行研究,所研究的调度环境为假设工件集N的n个工件在一台机器上进行无中断的加工,每个工件的加工时间、到达时间和交工日期分别为pi,ri和di,且每个工件在零时刻到达,即ri=0,其完工时间为Ci,流程时间Fi=Ci-ri=Ci,平均流程时间(F)=n∑i=1Fi/n.     

DEDS的集结与输入-输出等价

作者对有限缓冲器容量的柔性制造系统(FMS)建模,并对所建的高维模型完成了集结和保持输入-输出等价的算法.该模型和集结、输入-输出等价算法已成功地用于FMS的摄动分析. 设有M台机床,m种工件.设工件访问机床的次序不逆向,但并不要求工件必须顺序经过M台机床. 记u_i(1≤i≤M)为i机床投入运行时刻;(M+1≤i≤M+m)为(i—M)工件投料时刻;x_(ij)为j机床加工i工件的开始时刻;y_i(1≤i≤m)为i工件加工完毕时刻;(m+1≤i≤m+M)为(i—m)机床加工完毕时刻;a_(ij)为j机床加工i     

并行机含调整时间成套订单数问题遗传算法

为使总加权成套订单延迟数最小,提出了一类新的目标排序问题-并行机带调整时间加权成套订单数问题.多个工件来自多个订单,分属多个不同组类.每个订单有一个权值,每个工件有确定的加工时间、交货期,且需在多台并行机上加工.每个工件只需在任一台机器上加工一次,只有所有属于某一订单的工件都在各自交货期内完工才称此订单成套完工.建立了问题的数学模型,设计了一种启发式遗传算法.通过算例分析及对随机产生的数据进行验证得出,遗传算法对于大中型成套订单问题是十分有效的.     

1998年第14期擂台赛点评

问题:已知n个点(n≤200),任意两个相邻点i,i+1之间都有m条边(2≤m≤10),每条边有一个权值f_(ij)(1≤i≤n-1,1≤j≤m) ,我们定义从第1点到第n点的所有路径中,长度除以b(2≤b≤50)的余数最小的路径是最优路径。试编一程序求最优路径。     

基于离散对数上的多级多代理签名方案

通过对代理多重数字签名、多重代理数字签名和多级代理数字签名方案的深入研究,结合三者的思想,提出了一个基于离散对数上的多级多代理数字签名方案,前三者均可以看作该签名的特殊形式,即若Aij(1≤j≤ni)是Ai-1j信任的第i级代理签名人,当i=1,n0＞1,n1=1时该签名就是代理多重签名;当i=1,n0=1,n1＞1时该签名就是多重代理签名;当i＞1,n0=1,…,ni=1是该签名就是多级代理签名.本方案不仅具有前三者签名类型的优点,而且更具有一般性,应用范围也更加广泛.     

线性规划中的多项式型算法

<正> 我们考虑由具有整系数a_(ij),b_i的关于n≥2个实变元x_1,…,x_j,…,X_n的m≥2个线性不等式 a_(il)X_1+…+a_(in)X_n≤b_i i=1,2,…,m(1)所组成的系统。令 L=[sum from i,j=1 to m,n(log_2(|a_(ij)|+1))+sum from ?=1 to m(log_2(|b_i|+1)+log_2nm)]+1 是系统的输入的长度,亦即为了把(1)写成二进制形式所需要的符号0,1的个数。     

学生体质综合评价的诸成份比例分析方法及其微机管理系统

一、诸成份比例分析方法介绍1.求各类指标的权重设i代表年龄,(i=1,2,…,16),j代表各类指标(j=1,…,10),X(i,j)代表第i个年龄组的第j个指标的均值,B(i,j)代表第i个年龄组第j个指标的百分数.1)求同一指标不同年龄组各实测的均值X     

Ω上三重积分优化复化Simpson数值算法

设空间区域 Ω={(x,y,z)|α≤x≤b,φ_1(x)≤y≤φ_2(x),φ_1(x,y)≤z≤φ_2(x,y)}。(1)f(x,y,z)在Ω及其邻域内具有四阶连续偏导数,φ_1(x)与φ_2(x)在[α,a]内可导,φ_1(x,y)与φ_2(x,y)在Ω的投影(xoy面)区域上具有连续偏导数。下面介绍三重积分 I=∫∫∫f(x,y,z)dxdydz (2)的优化复化Simpson数值积分算法。首先将Ω进行划分,把[α,b]分为2m等分,步长与分点为 h_1=(b-α) /2m,x_i=α+ih_1(i=0,1,2,…,2m)。 (3)在x_(2i+1)处把[φ_1(x_(2i+1)),φ_2(x_(2i+1))分为2n等分,步长与分点为 g_(1,2i+1) =((φ_2(x_(2i+1)))-(φ_1(x_(2i+1))))/2n (i=o,1,2,…,m-1), (4) y_(2i+1,j)=φ_1(x_(2i+1))+jg_(1,2i+1) (j=0,1,2,…,2n)。     

推导万年星期历的Turbo-C程序

在这个表中我们只要知道日期、月份、年份,则可通过查表找出这个日期所对应的是星期几.具体找法是:找出日期所在的行i1(i1=0,1,2…6);找出月份所在的列j1(j1=0,1,2…6).则(i1,j1)就对应表中的”字母方阵”中的一个固定的字母(n,z,w,l,x,q,j);再找出年份对应的列j2(j2=0,1… 6);在”字母方阵”的 j2列中找与(i1,j1)对应的字母匹配的字母,这个字母所在行i2(i2=0,1……6)的最后一列的字符就是星期几的代码.例如:1995年7月21日.我们首先找出21日所在的行是第7行(i1=6),7月所对应的列是第2列     

批处理机上具有两类释放时间的工件集竞争调度问题

研究了两个工件集合竞争在一台批处理机上加工的调度问题,其中每个集合的工件具有一个共同的释放时间.批处理机可以同时加工多个工件作为一批,每批的加工时间为该批工件中加工时间的最大值.基于两类释放时间的大小,针对无界批处理机上最小化一个集合工件的最大完工时间、最大延迟以及总完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,分别给出了最优求解方法.针对有界批处理机上最小化一个集合工件的最大完工时间,使得另一个集合工件的最大完工时间不超过给定上界问题,证明为一般意义NP-难问题,并给出伪多项式时间最优求解方法.     

双n次曲面凸性的判别

矩形域上双n次曲面片的一般表达式为 z=[x~n,…,x,1]A[y~n…y 1],0≤x,y≤1,(1.1)其中A=[α_(i,j)]_(1≤i,j≤n 1)为n 1阶的实矩阵。在计算机辅助几何设计中所使用的曲面常常是由这样的一些曲面依一定的连接条件拼接而成的。对n为3的特殊情形,文献[1]给出了这类曲面凸性的几个充分条件。本文试图将该文结论作一推广,同时尝试将多项式理论中的Budan-Fourier定理以及Descarte的符号规则用于对曲面片(1.1)的凸性     

国防科技大学研究生院一九九九年硕士生入学考试软件基础试题(上)

一、 (共 40分 ) PASCAL语言部分以下 1至 3题均为程序填空 ,请按各题的程序及其说明填入正确内容 ,使程序完整 (每空 3分 )。1.[程序说明 ]寻找并输出 2 0 0 0之内的所有回文数。所谓回文数指正读与反读都一样的正整数 ,如 5 5 ,12 1等。要求每行输出 10个数。[程序 ]PROGRA M palindrome( output) ;VAR n,m ,i,j,k:integer;d:ARRA Y[1..10 ] OF integer;BEGINk:=0 ;F OR n:=1TO 2 0 0 0 DOBEGINm:=n;　　　　 j:=0 ;WH IL E m<>0 DOBEGINj:=j 1d[j] :=　　 ( 1)　　 ;m:=m DIV 10EN D;i:=1;WHIL E　　 ( 2 )　…     

解实对称矩阵特征值并行快速Jacobi方法

<正> 本文对传统的Jacobi 变换进行变形,且在此基础上设计了快速方法。对一次扫描而言,进行变形可省2·(((n(n-1))/2)-2[(n+1)/2]+1)次矩阵乘法([x]表示≤x 的最大整数),快速方法对固定j 而言,省了一次开平方计算。一、Jacobi 变换变形对n 阶实对称矩阵A=[a_(ij)=[(?)]i,j=1,2,…n,鉴于A 的对称性,仅考虑i相似文献   

FoxBASE逐步回归分析程序

FoxBASE逐步回归分析程序,能直接使用数据库,进行回归分析计算,免去了用高级语言去读取数据库或数据库的文本文件方式,提高了运算速度,加强对大数量资料的管理功能。对原始数据可进行追加、修改、查询、删除,使用户在校对中减少疲劳,提高了功效。其程序编制方法:首先对相关系数矩阵r(i,j)(i,j≤1,2…,m+1)用PUBLIC来设置,不用DIMENSION数组说明,以免变量找不到,变量个数m=fcount ();样本含量n=reccount ()均由微机自动计入。第二数据资料输入方式在循环语句中,可用scalter to X与skip相结合方式,一次读入m个变量值,记录全部读入完即循环结束,并进行一般计算,构成一个相关系数矩     

一类两阶段杂交流水作业的近似算法?

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务：第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作 NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

一类两阶段杂交流水作业的近似算法

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.     

一个Bottleneck问题及其算法

在文[1]中,提出了下面的数学模型:模型Ⅱ.求-X=(x_1,x_2,…,x_n)满足下列约束条件 sum from j=1 to n(x_j=m)(m≥n且为整数), x_j≥1 且为整数,j=1,2,…,n,     

线性最小二乘逼近的定向扰动分析

一 给定数据点对x_i～y_i,i=1,2,…,m(1.1)及拟合基函数系{(?)_j(x)},j=1,2,…,n,(1.2)并记Φ(x)=((?)_1(x),(?)_2(x),…,(?)_n(x))~r。     

工件具有不同尺寸单台批处理机的调度问题

n个工件要在一台有高度限制的批处理机上分批进行加工,工件j的加工时间和高度分别为Pj和Sj,批的加工时间为批中加工时间最大的工件的加工时间,每批加工时,机器的剩余量为批处理机的高度与批中工件的高度和之差,目标函数最小化机器空余总量和工件总完成时间,该NP-难问题源于钢铁企业的罩式退火炉调度问题.基于部分工件分批性质,提...     

基于佳点集遗传算法求解Job—shop调度问题

1.介绍 Job-shop调度问题(JSSP)是极为困难的带约束组合优化问题,是NP难的。典型的Job-shop调度问题可描述为n个工件要在m台机器上加工,每个工件有其特定的加工工序,每道工序加工时间已知,并符合以下假设: (1)每个机器在同一时刻只能加工一个工件。(2)每个工件的工序事先确定。(3)同一工件的两个工序不可同时进行。(4)不允许抢占式执行,即一个工序执行后就不能中断。(5)机器间传送时间为零。典型的调度目标是确定每个机器上工序的加工顺序和各工序的开始时间,以使完成所有工序所需的时间(Makespan)最少。