生产调度作业题库及答案

生产调度作业题库及答案一、单项选择题（本大题共20小题，每小题1分，共20分）1.在生产调度问题1||中，目标函数A.最大完工时间B.总完工时间C.最大延迟时间D.总延迟时间2.对于单机调度问题1|A.最短加工时间优先（SPT）B.最早工期优先（EDD）C.加权最短加工时间优先（WSPT）D.最长加工时间优先（LPT）3.Johnson法则主要用于解决（）调度问题。A.单机调度B.并行机调度C.两台机器的流水作业调度D.作业车间调度4.在流水车间调度中，若所有工件在各台机器上的加工顺序都相同，则称为（）。A.作业车间B.开放车间C.流水车间D.混合车间5.对于单机调度问题1|A.SPT规则B.EDD规则C.Moore-Hodgson算法D.LPT规则6.下列哪种调度规则属于优先权规则？（）A.分支定界法B.动态规划法C.最短松弛时间优先（SST）D.遗传算法7.在并行机调度问题P|A.P类问题B.NP-难问题C.线性规划问题D.凸优化问题8.为了最小化最大完工时间，在并行机调度中常用的启发式算法是（）。A.LPT（最长加工时间优先）B.SPT（最短加工时间优先）C.EDD（最早工期优先）D.FIFO（先进先出）9.调度问题JmA.m台机器的流水车间调度，目标是最小化最大完工时间B.m台机器的作业车间调度，目标是最小化最大完工时间C.m台机器的开放车间调度，目标是最小化最大完工时间D.单机调度，目标是最小化最大延迟10.在调度理论的三参数表示法α|β|A.机器环境B.工件特征C.目标函数D.约束条件11.下列关于关键路径的说法，错误的是（）。A.关键路径的长度决定了项目的最短可能工期B.关键路径上的工序总时差为零C.一个网络图中只能有一条关键路径D.关键路径上的工序延迟会导致整个项目延迟11.Moore-Hodgson算法用于解决单机调度问题（）。A.1B.1C.1D.112.在两台机器的流水车间调度中，若工件j在第一台机器上的加工时间小于在第二台机器上的加工时间，根据Johnson法则，该工件倾向于（）。A.排在序列的前部B.排在序列的后部C.排在序列的中间D.位置任意13.调度中的“机器阻塞”是指（）。A.机器发生故障B.工件在当前机器加工完后，因下游机器忙而无法离开，占用当前机器C.没有工件分配给机器D.操作员操作失误14.对于F2A.该问题等同于普通F2B.该问题可用Gilmore-Gomory算法求解C.该问题只能用枚举法求解D.该问题总是无解15.在调度问题中，表示（）。A.工件j的加工时间B.工件j的到达时间C.工件j的工期D.工件j的权重16.下列目标函数中，属于正则目标函数的是（）。A.∑（总完工时间）B.∑（误工工件数）C.（最大延迟）D.以上都是17.在求解1||时，若所有工件A.任意顺序结果相同B.必须使用SPT规则C.必须使用EDD规则D.不可解18.分支定界法在解决调度问题时，主要用于（）。A.寻找大规模问题的近似解B.寻找小规模问题的精确最优解C.实时动态调度D.随机调度19.在柔性流水车间中，若某工序有k台并行机，则（）。A.任意工件必须经过所有k台机器加工B.工件只需在k台机器中选择一台加工即可C.k台机器必须同时加工同一工件D.工件在该工序的加工时间是单台机器的120.遗传算法是一种基于（）的全局优化搜索算法。A.微积分原理B.梯度下降C.自然选择和遗传机制D.确定性遍历二、多项选择题（本大题共10小题，每小题2分，共20分。多选、少选、错选均不得分）1.按照机器环境的不同，生产调度问题主要可以分为（）。A.单机调度B.并行机调度C.流水车间调度D.作业车间调度E.开放车间调度2.下列哪些属于常见的调度目标函数？（）A.最小化最大完工时间()B.最小化总完工时间(∑)C.最小化最大延迟()D.最小化误工工件数(∑)E.最大化机器利用率3.关于SPT（最短加工时间优先）规则，下列描述正确的有（）。A.它是1|B.它是1|C.它通常能减少在制品库存（WIP）D.它总是能最小化最大完工时间E.它不考虑工件的工期4.下列哪些算法属于精确算法？（）A.动态规划B.分支定界C.模拟退火D.禁忌搜索E.割平面法5.在作业车间调度中，确定一个可行调度通常需要确定（）。A.每台机器上工件的加工顺序B.每个工件的开始加工时间C.每个工序的加工机器D.工件的优先级E.机器的维护时间6.造成调度问题复杂性的因素包括（）。A.工件到达的动态性B.机器环境的不确定性（如故障）C.工序之间的约束关系D.存在准备时间E.目标函数的非线性7.对于并行机调度问题，机器可以分为（）。A.同速机B.异速机C.同类机D.不相关机E.虚拟机8.在求解Fm||A.Johnson法则B.Palmer算法C.Gupta算法D.CDS算法E.NEH算法9.下列关于误工时间和延迟的关系，正确的有（）。A.=B.=C.若<0，则D.总是等于E.可以是负数，但非负10.下列哪些技术常用于现代智能优化算法以解决复杂的调度问题？（）A.禁忌列表B.交叉与变异操作C.温度冷却机制D.蚁群信息素更新E.单纯形表三、填空题（本大题共10小题，每小题2分，共20分）1.在调度符号α|β|2.对于单机调度问题1|3.Johnson法则判断工件i排在工件j前面的条件是mi4.在作业车间调度中，描述工序加工顺序的有向图称为________。5.若一个调度问题可以在多项式时间内找到最优解，则称该问题属于________类问题。6.对于1||问题，若按EDD规则排序，则最大延迟7.在考虑工件准备时间的调度中，若准备时间与加工顺序有关，则通常记为，表示________。8.为了最小化最大完工时间，LPT算法在分配工件时，总是将当前未分配的加工时间________的工件分配给当前负载最小的机器。9.在资源受限的项目调度问题中，________是核心约束条件。10.分支定界法中，________用于剪除那些不可能产生优于已知最优解的分支。四、简答题（本大题共4小题，每小题5分，共20分）1.简述正则目标函数的定义，并举例说明。为什么在正则目标函数下，工件之间如果有空闲时间是可以消除的？2.简述Johnson法则解决两台机器流水车间调度问题（F23.比较流水车间调度与作业车间调度的主要区别。4.简述模拟退火算法的基本原理及其在解决生产调度问题中的优缺点。五、计算与分析题（本大题共3小题，每小题10分，共30分）1.设有5个工件需在一台机器上加工，其加工时间和工期如下表所示。请分别使用SPT规则和EDD规则排出加工顺序，并计算各自序列下的最大完工时间、最大延迟以及总完工时间∑。工件$j$12345加工时间$p_j$37425工期$d_j$61248102.有6个工件需要在2台机器上加工，加工顺序均为先机器1后机器2。各工件在机器上的加工时间如下表所示。请利用Johnson法则求出最优加工顺序，并计算该顺序下的最大完工时间（画出甘特图辅助计算说明）。工件$j$123456机器1时间$p_{1j}$528463机器2时间$p_{2j}$4635273.设有4个工件,,,，需在3台机器P=[其中行代表机器，列代表工件。请使用CDS算法（Campbell,Dudek,Smithalgorithm）构造一个近似的调度序列以最小化最大完工时间。要求写出详细的构造虚拟两台机器的时间过程。六、综合应用题（本大题共2小题，每小题20分，共40分）1.某车间接到4个工件的加工任务，每个工件包含3道工序，需在3台不同的机器上加工，但工序的加工顺序可以任意（开放车间调度问题O32(1)请利用基于长路径的启发式策略或通过逻辑分析，构造一个最大完工时间较短的可行调度方案。(2)画出该调度方案的甘特图。(3)计算该方案的最大完工时间。(4)简述开放车间调度与流水车间调度在约束上的根本区别。2.某工厂有一台关键设备，今有5个订单需要在该设备上加工。各订单的加工时间、权重和工期如下表所示。工厂的目标是最小化加权总完工时间∑。订单$j$12345$p_j$48365$w_j$21321(1)请证明对于问题$1\sumw_jC_j$，WSPT规则（即按$p_j/w_j$非减顺序排列）是最优算法。(2)利用WSPT规则确定上述5个订单的最优加工顺序。(3)计算该最优顺序下的目标函数值∑。(4)若工厂现在更关注误工情况，目标改为最小化误工工件数∑，且已知各订单的工期d=参考答案与解析一、单项选择题1.A解析：即MaxCompletionTime，表示最后一个完工工件的完工时间，也称为制造周期。2.C解析：对于1||∑3.C解析：Johnson法则是解决两台机器流水车间调度问题F24.C解析：所有工件以相同的顺序经过所有机器，这是流水车间的定义。5.B解析：对于单机最大延迟问题1|6.C解析：SST（ShortestSlackTime）是一种基于优先权的分派规则。A、B是精确算法，D是元启发式算法。7.B解析：P||指同速并行机调度，目标是最小化最大完工时间。即使8.A解析：LPT（LongestProcessingTimefirst）是针对Pm9.B解析：J代表JobShop（作业车间），m代表机器数量，代表目标。10.B解析：α是机器环境，β是工件特征及约束（如释放时间，准备时间等），γ是目标函数。11.C解析：一个网络图中可以存在多条关键路径，只要它们的长度相等且最长。12.A解析：Moore-Hodgson算法用于最小化误工工件数∑。13.B解析：Johnson法则中，若min(,)<min14.B解析：机器阻塞是指下游机器忙，导致工件无法移走，从而阻塞了当前机器，使其无法加工下一个工件。15.B解析：Gilmore-Gomory算法是解决F216.B解析：是Releasetime，即工件到达时间，可开始加工的时间。17.D解析：正则目标函数是指目标函数值是非减的关于完工时间的函数。∑、∑、都是正则的。18.A解析：若所有=0，则1||变为119.B解析：分支定界法是用于寻找组合优化问题精确最优解的算法，适用于小规模问题。20.B解析：柔性流水车间中，并行机是互斥的，工件只需选一台加工。21.C解析：遗传算法是模拟生物进化过程（选择、交叉、变异）的搜索算法。二、多项选择题1.ABCDE解析：这五类是机器环境的基本分类。2.ABCD解析：机器利用率通常是工程指标，但在调度理论中，最小化等价于最大化机器利用率，不过作为目标函数符号γ，通常指前四类。3.ACE解析：SPT是∑的最优解；能减少WIP；不考虑工期。B是错的，因为WSPT才是∑的最优；D是错的，SPT不优化。4.ABE解析：动态规划、分支定界、割平面法是精确算法。模拟退火和禁忌搜索是元启发式算法。5.AB解析：确定作业车间调度主要是确定每台机器上的工件顺序（A）和每个工序的开始时间（B）。C在作业车间中是已知的（工艺路线）。6.ABCDE解析：这些都是导致调度问题复杂且难以求解的因素。7.ABCD解析：并行机分为同速机、异速机、同类机、不相关机。8.BCDE解析：Johnson法则仅适用于2台机器。对于m≥9.ABCE解析：=−，可正可负；=10.ABCD解析：A是禁忌搜索，B是遗传算法，C是模拟退火，D是蚁群算法。单纯形表是线性规划方法。三、填空题1.流水车间2.加工时间()3.任意顺序(或顺序不影响)4.析取图5.P6.最小(或取得下界)7.工件j紧前加工为i时的准备时间8.最长9.资源数量10.下界四、简答题1.答：正则目标函数是指目标函数γ(,…,)关于每个完工时间是非减的。即如果常见的例子包括：最大完工时间=max(,原因：在正则目标函数下，推迟任何工件的开工时间（在不违反其他约束的情况下）只会增加或保持其完工时间，从而不会使目标函数值变小。因此，机器在加工完一个工件后如果有空闲时间，完全可以将后续工件提前加工，消除空闲时间而不会导致目标函数变差。2.答：Johnson法则步骤如下：(1)将工件集分为两个子集：集合I包含满足<的工件，集合II包含满足>的工件。若=(2)将集合I中的工件按照（第一台机器上的加工时间）的非减顺序排列。(3)将集合II中的工件按照（第二台机器上的加工时间）的非增顺序排列。(4)最优序列为集合I的序列紧接着集合II3.答：(1)工艺路径：流水车间中，所有工件的工艺路径相同，即均依次经过,,(2)约束复杂性：流水车间主要受限于工件在同一条流水线上的先后顺序；作业车间除了每台机器上的工件顺序约束外，还受同一工件不同工序之间的先后约束（优先约束），这通常用析取图描述，求解难度更高。(3)机器环境：流水车间是作业车间的一个特例。4.答：基本原理：模拟退火算法源于金属退火物理过程。它通过设定一个初始温度，在高温下允许以一定概率接受恶化解（即目标函数值变差的解），从而跳出局部最优；随着温度逐渐降低，接受恶解的概率逐渐减小，最终在低温下趋于稳定，找到全局最优解的近似。优点：能够跳出局部最优，具有很强的全局搜索能力，适合解决复杂的组合优化问题（如复杂的调度问题）。缺点：收敛速度通常较慢；参数（初始温度、冷却率、终止条件）的选择对算法性能影响很大；单次运行结果可能不稳定。五、计算与分析题1.解：(1)SPT规则(按升序):排序：=顺序：→计算完工时间：======∑计算延迟=−======(2)EDD规则(按升序):排序：=顺序：→计算完工时间：======∑计算延迟=−======结果汇总：SPT顺序：4-1-3-5-2，=EDD顺序：3-1-4-5-2，=2.解：应用Johnson法则：列出各工件的最小加工时间及对应机器：:m:m:m:m:m:m步骤：1.全局最小值为2（的M1，的M2）。2.选（M1），排前面。序列：[,?,?3.剩余最小值为2（的M2）。4.选（M2），排后面。序列：[,?,?5.剩余最小值为3（的M1，的M2）。6.选（M1），排前面。序列：[,,?,7.剩余最小值为3（的M2）。8.选（M2），排后面。序列：[,,?,9.剩余最小值为4（的M2，的M1）。10.选（M1），排前面。序列：[,,,?11.剩余。序列：[,,最优顺序：→计算最大完工时间：顺序：2,6,4,1,3,5时间矩阵：::机器1完工时间：======机器2完工时间（需考虑机器依赖）：=======甘特图描述：M1:J2(0-2),J6(2-5),J4(5-9),J1(9-14),J3(14-22),J5(22-28)M2:J2(2-8),J6(8-15),J4(15-20),J1(20-24),J3(24-27),J5(27-29)--Wait,calculationcheckRecheckCalc:=mM2:J2(2-8),J6(8-15),J4(15-20),J1(20-24),J3(24-27),J5(27-30).Correct.3.解：CDS算法步骤：CDS算法通过构造m−这里m=3，需构造问题k=虚拟机器1时间=虚拟机器2时间=计算得：::::对矩阵[[(排序逻辑：(2<7,前)(3<9,前)(4<8,前)(5<11,前)序列1：3→1→问题k=虚拟机器1时间=虚拟机器2时间=计算得：::::对矩阵[[((5(5(7比较过程：最小值是4(P2)，放后面。Set:[?,剩余(5(5,5),任意。放前面？通常剩余(5(5,6放最后。序列2：3→1→比较两个序列：计算序列1(,,,)的(2(3(4(5=计算序列2(,,,)的(2(3(5(4=结论：CDS算法得到的近似最优序列为→→六、综合应用题1.解：(1)构造调度方案：对于O3观察加工时间：:2:4:3:2策略：尽量让机器连续工作。尝试构造一个基于关键机器的序列。M2的总负荷最大(3+1+5+让我们尝试一个具体的逻辑序列：时刻0：M1加工(2),M2加工(时刻2：M1空闲，选(2)(M2需2，M3需3)。M1加工时刻4：M1空闲，选(4)。M1加工时刻5：M2空闲(完)，选(3)(M1完于5，M3需4)。M2加工(时刻6：M1空闲，选(3)。M1加工时刻8：M2空闲(完)，选(2)。M2加工(时刻9：M3空闲(完)，选(4)。M3加工(时刻10：M2空闲(完)，选(1)。M2加工(时刻11：M1空闲(完)，无待加工。时刻13：M3空闲(完)，选(3)。M3加工(时刻14：M2空闲(完)，无待加工。时刻16：M3空闲(完)，选(2)。M3加工(时刻18：结束。=18让我们验证一下这个方案的可行性并画出甘特图。机器分配：M1:(M2:(M3:(检查约束：:M1(0-2),M2(5-8),M3(9-13).OK.:M1(4-8),M2(10-11),M3(0-2).OK.:M1(8-11),M2(0-5),M3(16-18).OK.:M1(2-4),M2(8-10),M3(13-16).OK.该方案=18(2)甘特图：```M1:|J1|J4|---J2---|J3|024811M2:|----J3----|J1|J4|J2|0