生产调度考试卷及答案

生产调度考试卷及答案一、单项选择题（本大题共25小题，每小题1分，共25分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。）1.生产调度问题的基本描述通常包括机器、工件和（）。A.路径B.加工顺序C.目标函数D.工艺约束2.在流水车间调度问题中，若所有工件在各机器上的加工顺序相同，则称为（）。A.作业车间B.开放车间C.置换流水车间D.混合流水车间3.下列调度规则中，以“加工时间最短优先”为原则的是（）。A.FCFS（先来先服务）B.SPT（最短加工时间）C.EDD（最早交货期）D.LPT（最长加工时间）4.Johnson算法主要用于解决（）的调度问题，以最小化最大完工时间。A.单台机器B.两台机器流水作业C.多台机器作业车间D.并行机调度5.衡量调度方案优劣的指标中，表示（）。A.平均完工时间B.最大完工时间（Makespan）C.最大延误时间D.总流程时间6.对于单机调度问题，若目标是最小化平均流动时间，最优的调度规则是（）。A.EDDB.SPTC.MWKR（剩余加工时间最大者优先）D.CR（关键比最小者优先）7.下列哪种情况属于NP-hard问题？（）A.1B.FC.JD.P8.在调度中，如果工件i的完工时间大于其交货期，则该工件的延误为（）。A.−B.−C.mD.m9.Palmer启发式算法主要用于解决（）调度问题。A.单机B.流水车间C.开放车间D.柔性作业车间10.在资源受限的项目调度中，关键路径法（CPM）的主要局限性在于（）。A.不能计算工期B.假设资源是无限的C.只能用于小型项目D.无法确定关键活动11.调度问题表示法n|m|A.工件数B.机器数C.约束条件D.目标函数12.用于求解复杂调度问题的现代元启发式算法不包括（）。A.遗传算法（GA）B.模拟退火（SA）C.Johnson算法D.禁忌搜索（TS）13.在作业车间调度中，允许一个工件在同一台机器上加工多次的情况称为（）。A.重入型调度B.开放调度C.混合调度D.动态调度14.下列哪个指标属于正则指标？（）A.最大完工时间B.提前/拖期惩罚C.库存成本D.设备利用率（非时间类指标需谨慎，此处指随完工时间单调变化的时间指标）15.采用SPT规则调度的主要优点是（）。A.保证了交货期B.最大化设备利用率C.最小化平均在制品库存D.最小化最大完工时间16.在柔性作业车间调度（FJSP）中，与作业车间调度（JSP）的主要区别在于（）。A.工件加工路径不确定B.机器具有多加工能力，工序可选机器集大于1C.目标函数不同D.必须使用智能算法求解17.考虑机器准备时间的调度问题中，如果准备时间依赖于加工顺序，这被称为（）。A.序相关准备时间B.序独立准备时间C.随机准备时间D.固定准备时间18.瓶颈资源理论（TOC）中，用于控制生产物流节奏的工具是（）。A.甘特图B.DBR（鼓-缓冲-绳子）C.PERT图D.平衡线图19.在并行机调度中，若各机器加工速度不同，则称为（）。A.同速机B.异速机C.不相关机D.专用机20.对于目标为最小化最大延误时间的单机调度问题，最优规则是（）。A.SPTB.EDDC.Moore-Hodgson算法D.WSPT21.下列哪种编码方式常用于遗传算法解决置换流水车间调度？（）A.二进制编码B.实数编码C.基于工件的排列编码D.矩阵编码22.生产调度中的“死锁”现象通常发生在（）。A.单机环境B.资源共享且存在循环等待的复杂环境C.只有FCFS规则下D.无限缓冲区情况下23.动态调度与静态调度的根本区别在于（）。A.调度算法不同B.是否考虑工件到达时间的动态性及随机干扰C.机器数量不同D.目标函数不同24.NEH算法是解决（）问题的一种高效的构造型启发式算法。A.单机调度B.置换流水车间调度（以最小化最大完工时间为目标）C.并行机调度D.项目调度25.在进化计算中，维持种群多样性的常用操作是（）。A.选择B.交叉C.变异D.复制二、多项选择题（本大题共10小题，每小题2分，共20分。在每小题列出的五个备选项中至少有两个是符合题目要求的，请将其代码填写在题后的括号内。多选、少选、错选均不得分。）1.生产调度的基本要素包括（）。A.机器B.工件C.目标函数D.加工路线E.车间温度2.常见的调度性能指标包括（）。A.最大完工时间B.总流动时间C.最大延误D.机器利用率E.工人满意度3.以下哪些属于流水车间调度问题的约束？（）。A.每个工件包含多道工序B.所有工件在各机器上的加工顺序相同C.一台机器同一时刻只能加工一个工件D.一个工件同一时刻只能在一台机器上加工E.工序可以中断4.求解NP-hard调度问题的常用方法包括（）。A.精确算法（如分支定界法）B.启发式规则C.元启发式算法（如遗传算法、蚁群算法）D.简单的枚举法E.仅靠经验估计5.以下关于SPT规则的说法，正确的有（）。A.能最小化平均完工时间B.能最小化平均流动时间C.通常会增加在制品数量D.可能导致加工时间长的工件长时间等待E.总是最优的6.柔性作业车间调度问题比一般作业车间调度问题更复杂，原因在于（）。A.需要确定工序的加工顺序B.需要为每道工序选择机器C.机器数量更多D.工件数量更多E.目标函数无法计算7.典型的调度图示化工具包括（）。A.甘特图B.排列图C.网络图D.鱼骨图E.直方图8.在考虑设备维护的调度中，维护策略通常包括（）。A.预防性维护B.纠正性维护C.视情维护D.随机维护E.无维护9.影响调度问题复杂度的因素包括（）。A.工件数量B.机器数量C.缓冲区大小D.是否允许中断E.车间光照10.下列哪些是蚁群算法（ACO）的特性？（）。A.正反馈机制B.分布式计算C.启发式搜索D.只能解决TSP问题E.必须使用实数编码三、填空题（本大题共15小题，每小题1分，共15分。请将正确答案填写在题中横线上。）1.在调度问题的三参数表示法α|β|γ中，2.对于单机调度问题1|3.Johnson算法判断工件i应排在前面还是后面的条件是：比较min(,)4.在运筹学中，流水车间调度问题F35.调度中的“空闲时间”是指机器处于________状态的时间段。6.在交货期窗口调度中，如果工件在交货期窗口内完工，则不受惩罚，否则受到惩罚，这属于________指标。7.Palmer算法中，斜度指标的计算公式涉及________。8.遗传算法模拟生物界的自然选择和________机制进行搜索。9.禁忌搜索算法中，为了防止循环，使用________表来记录刚走过的路径。10.在动态调度中，常见的重调度策略包括________、周期性重调度和事件驱动重调度。11.CDS算法是将流水车间问题转化为一系列________机器问题的启发式算法。12.异速并行机调度问题中，机器j的速度为，工件i在机器j上的加工时间=/，若速度差异是非线性的，则称为________并行机。13.常用的局部搜索邻域结构包括交换、插入和________。14.提前/拖期惩罚问题中，理想目标是使工件的完工时间等于其________。15.生产调度的解通常表示为________或机器甘特图。四、判断题（本大题共10小题，每小题1分，共10分。正确的打“√”，错误的打“×”。）1.所有的流水车间调度问题都是多项式时间可解的。（）2.SPT规则在最小化最大完工时间这一指标上通常表现优异。（）3.作业车间调度中，不同工件的加工顺序可以不同。（）4.禁忌搜索算法肯定能找到全局最优解。（）5.准备时间与加工顺序无关时，可以将准备时间合并到加工时间中处理。（）6.在无限缓冲区的流水车间中，阻塞现象永远不会发生。（）7.模拟退火算法在高温时接受恶化解的概率较大。（）8.关键路径上的工序延误一定会导致整个项目的完工期延误。（）9.单机调度问题1|10.柔性作业车间调度的解空间包含传统作业车间调度的解空间。（）五、简答题（本大题共6小题，每小题5分，共30分。）1.简述生产调度问题中，ActiveSchedule（活跃调度）、Non-delaySchedule（无延迟调度）和Semi-activeSchedule（半活跃调度）的定义及三者之间的关系。2.简述Johnson算法求解两台机器流水车间调度问题的基本步骤和适用条件。3.解释什么是调度问题的“计算复杂性”，并说明P类问题、NP类问题及NP-hard问题的区别。4.列举三种常见的调度规则，并分别说明它们主要优化的目标指标。5.简述遗传算法在解决生产调度问题时的基本流程（包括编码、选择、交叉、变异等步骤的作用）。6.在动态生产环境中，常见的干扰因素有哪些？请列举至少四种，并简述其对调度的影响。六、计算题（本大题共3小题，每小题15分，共45分。）1.设有5个工件,,,,需要在单台机器上加工，其加工时间和交货期如下表所示。请分别使用SPT规则和EDD规则进行排序，并计算每种排序下的最大完工时间、最大完工时间对应的平均流程时间¯F以及最大延误。工件$J_1$$J_2$$J_3$$J_4$$J_5$加工时间$p_j$37254交货期$d_j$816410122.某流水车间有2台机器和，有6个工件需经这两台机器加工，顺序均为先后。各工件在机器上的加工时间见下表。请使用Johnson算法求出最优加工顺序，并计算该顺序下的最大完工时间（Makespan）。工件$J_1$$J_2$$J_3$$J_4$$J_5$$J_6$$M_1$(时间)5183106$M_2$(时间)4295783.考虑一个3×:(3:(3:(2(1)请画出该问题的析取图模型（描述节点、弧的含义）。(2)利用图论中的关键路径概念，计算给定顺序下的Makespan（假设没有特定的机器顺序约束，你可以通过甘特图寻找一个可行解并计算其Makespan，或者使用移动瓶颈法的基本逻辑尝试寻找较优解，此处仅需画出一种可行调度甘特图并计算对应的Makespan）。七、案例分析题（本大题共1小题，共10分。）某汽车零部件制造车间主要生产发动机缸体，该车间是一个典型的柔性作业车间（FJSP）。车间内有4台加工中心（编号为M1,M2,M3,M4），每台机器都能完成多种工序，但效率不同。车间实行两班倒工作制。最近，车间面临以下问题：1.订单多为多品种、小批量，换型频繁。2.经常出现机器故障，导致原定生产计划无法按时完成。3.急单插单现象严重，导致在制品（WIP）库存积压严重，交货期延误率上升。现在车间主任决定引入一套高级计划与排程系统（APS）。作为调度专家，请你分析：1.针对该车间的特点，应采用静态调度还是动态调度？为什么？2.在建立调度模型时，除了最小化最大完工时间外，还应该考虑哪些关键目标？3.针对机器故障和急单插单，应采取什么样的重调度策略？参考答案及详细解析一、单项选择题1.C解析：生产调度问题三要素是资源（机器）、任务（工件）和目标（目标函数）及约束。路径通常是约束的一部分，但广义的调度描述必须包含优化目标。2.C解析：流水车间中，若所有工件在所有机器上的加工顺序完全一致，称为置换流水车间。3.B解析：SPT即ShortestProcessingTime，最短加工时间优先。4.B解析：Johnson算法是解决F25.B解析：（Makespan）指最后一个工件完工的时间，即最大完工时间。6.B解析：对于1||¯7.C解析：1||任意顺序，F2||Johnson算法，P8.C解析：延误定义=−，拖期=ma9.B解析：Palmer算法是基于斜度指标的流水车间构造型启发式算法。10.B解析：关键路径法（CPM）主要关注时间逻辑，默认资源是无限的，不考虑资源冲突。11.B解析：调度符号表示中，中间部分m通常指机器数量，或环境描述的一部分（如Fm12.C解析：Johnson算法是精确的多项式算法，不是元启发式算法。13.A解析：工件多次回到同一机器加工，如半导体制造，称为重入型。14.A解析：正则指标指目标函数值随各工件完工时间的增加而不减（如最大完工时间、最大延误）。15.C解析：SPT缩短工件在系统停留时间，从而减少在制品（WIP）。16.B解析：柔性作业车间允许工序在多台机器上选择加工，这是核心区别。17.A解析：准备时间依赖于前后两个工件，称为序相关。18.B解析：TOC理论中的DBR（Drum-Buffer-Rope）即鼓（瓶颈）、缓冲、绳子。19.B解析：同速机速度相同，异速机速度不同但与工件无关，不相关机速度与工件均有关。通常泛指速度不同为异速或不相关，此处选异速最贴切。20.B解析：对于最小化最大延误，EDD规则是最优的。21.C解析：排列编码自然对应工件的加工顺序，适用于置换流水车间。22.B解析：死锁发生于循环等待资源，如多机器共享不同类型的有限资源时。23.B解析：动态调度处理随时间变化的任务到达和随机事件。24.B解析：NEH（Nawaz-Enscore-Ham）算法被认为是目前求解Fm25.C解析：变异操作引入新基因，维持种群多样性。二、多项选择题1.ABCD解析：生产调度的基本要素包括机器资源、加工对象（工件）、目标和工艺路线等约束。温度通常不考虑。2.ABCD解析：常见的包括时间类指标（,¯3.ABCD解析：流水车间约束包括工序顺序约束、机器占用约束（互斥性）、工件唯一性。E选项“工序可以中断”是非抢占式调度的反面，通常默认不允许中断（非抢占），故E错误。4.ABC解析：NP-hard问题常用精确算法（小规模）、启发式规则和元启发式算法求解。枚举法不可行，仅靠经验不科学。5.ABD解析：SPT最小化平均完工/流动时间，但长工件可能等待很久（长工件饥饿），不总是最优（取决于目标）。6.AB解析：FJSP需要解决两个子问题：路由（选机器）和排序。7.AC解析：甘特图最直观，网络图用于项目调度。8.ABC解析：常见的维护策略有预防性、纠正性、视情维护。随机维护是一种干扰，不是策略。9.ABCD解析：规模、缓冲、中断与否都影响复杂度。10.ABC解析：ACO具有正反馈、分布式、启发式特征。可用于TSP以外的调度问题。编码通常是实数或路径。三、填空题1.目标函数2.WSPT（加权最短加工时间优先）注：若权相等则为SPT。3.前面4.NP-hard注：F2||5.空闲6.非正则7.工序加工时间注：斜度索引计算公式为=[8.遗传（变异）9.禁忌10.滚动窗口11.两注：CDS算法基于Johnson算法，将m台机器问题分解为若干个2机问题。12.不相关13.逆序14.交货期15.加工顺序四、判断题1.×解析：3台及以上机器的流水车间调度通常是NP-hard的。2.×解析：SPT主要优化平均流程时间，对的优化效果不如LPT或特定启发式算法。3.√解析：这是作业车间与流水车间的核心区别。4.×解析：TS是启发式算法，不能保证找到全局最优，只能寻找局部最优。5.√解析：若准备时间只与工件有关，可加到该工件加工时间中。6.√解析：无限缓冲区意味着工件加工完可直接进入下一道工序或等待，不会阻塞当前机器。7.√解析：Metropolis准则允许以一定概率接受恶解以跳出局部最优。8.√解析：关键路径长度即为项目工期，其上工序延误必导致总工期延误。9.√解析：EDD（最早交货期）规则对1|10.√解析：JSP是FJSP的特例（每道工序可选机器集=1）。五、简答题1.答：半活跃调度：在不改变任何机器上工件加工顺序的情况下，没有任何操作可以提前开始而不改变其他操作的加工顺序。即没有任何操作可以左移。活跃调度：在不改变任何机器上工件加工顺序的情况下，没有任何操作可以延迟开始（即左移）而不推迟其他任何操作。即不可能通过改变操作顺序来缩短Makespan。无延迟调度：只要机器有空闲，且有工件等待加工，就立即开始加工。即没有任何机器在有空闲且有工件可加工时处于闲置状态。关系：无延迟调度集合⊂活跃调度集合⊂半活跃调度集合。最优调度必然存在于活跃调度集中。2.答：步骤：1.在所有工件的加工时间,中找出最小值。2.若最小值出现在第一台机器（）的加工时间中，则将该工件尽可能排在序列的前面；若最小值出现在第二台机器（）的加工时间中，则将该工件尽可能排在序列的后面。3.将该工件从集合中移除。4.重复上述步骤，直到所有工件都排完。适用条件：n个工件，2台机器的流水车间问题，目标是最小化最大完工时间（F23.答：计算复杂性：指解决一个问题所需的计算资源（时间、空间）随问题规模增长而变化的函数关系。区别：P类问题：存在多项式时间算法可解的问题（如F2NP类问题：可以在多项式时间内被“验证”解的正确性的问题。NP-hard问题：所有NP问题都能在多项式时间内归约到该问题。这类问题通常被认为不存在多项式时间的精确解法（如Jm4.答：FCFS(FirstComeFirstServed)：先来先服务。公平性好，通常作为基准，无特定优化目标，但平均性能一般。SPT(ShortestProcessingTime)：最短加工时间优先。主要优化平均完工时间、平均流动时间和在制品库存。EDD(EarliestDueDate)：最早交货期优先。主要优化最大延误时间。LPT(LongestProcessingTime)：最长加工时间优先。通常用于并行机调度以最小化，平衡负载。（注：任选三种解释即可）5.答：编码：将调度解转化为算法能处理的个体（如染色体），常用排列编码。选择：根据适应度函数（如Makespan的倒数）从种群中选择优良个体遗传到下一代，体现“适者生存”。交叉：将两个父代个体的部分结构进行重组生成新个体，旨在保留优良基因片段并探索新解。变异：以较小概率改变个体上的某些基因，引入新性状，维持种群多样性，防止早熟收敛。流程：初始化种群→计算适应度→选择→交叉→变异→终止判断（未满足则循环）。6.答：机器故障：导致正在加工的工件中断，需重新安排机器和该工件的后续工序。急单/插单：增加工件集合，可能需要打断当前计划或重新排定优先级。原材料短缺/延迟：导致工件无法按计划开始，造成机器空闲或调整顺序。加工时间波动：实际加工时间偏离预计，导致后续工序开始时间变化。工艺变更/返工：改变工件的加工路径或增加工序，破坏原有调度。六、计算题1.解：(1)SPT规则排序按加工时间从小到大排序：=顺序：→计算完工时间、流程时间（=）、延误=−：:=2,=:=2+3:=5+4:=9+5:=14+7结果：=¯=(2)EDD规则排序按交货期从小到大排序：=顺序：→计算完工时间、流程时间、延误=−：:=2,=:=2+3:=5+5:=10+4:=14+7结果：=¯=(注：本题特定数据下两种规则相同，但通常EDD更优)2.解：应用Johnson算法：列表,：(寻找最小值：1.最小值为1（,），排首位。顺序：...2.剩余最小值为2（已排），其次3（,），排当前首位。顺序：,...3.剩余最小值为4（,），排末位。顺序：,…。4.剩余最小值为5（已排），其次6（,），排当前首位。顺序：,,…。5.剩余最小值为7（,），排当前末位。顺序：,,…6.剩余，排中间。最终顺序：→计算最大完工时间（Makespan）：顺序工件$M_1$完工时间$M_2$完工时间1$J_2$11+2=32$J_4$1+3=4$\max(4,3)+5=9$3$J_6$4+6=10$\max(10,9)+8=18$4$J_3$10+8=18$\max(18,18)+9=27$5$J_5$18+10=28$\max(28,27)+7=35$6$J_1$28+5=33$\max(33,35)+4=39$Makespan=393.解：(1)析取图模型：节点：每个工件的每道工序。即,,实线弧（连结弧）：表示同一工件的先后约束，例如→，权重为前一工序时间。虚线弧（析取弧）：表示在同一台机器上加工的工序不能重叠，需选择方向。例如上有,,，它们之间存在双向析取弧，需决定谁先谁后。源点和汇点：代表开始和结束，权重0。(2)甘特图求解（可行解示例）：我们寻找一个基于优先级的简单可行解。尝试顺序：优先处理先到的或者基于启发式。假设机器顺序：M1:→M2:→M3:→时间推演：M1(3,4,3)[J1(3),J3(4),J2(3)]在:0-3需等完。设先做。稍作调整，找一个具体的调度方案。方案构建：1.J1:M1(0-3)->M2(3-5)->M3(5-6)2.J2:M2需等J1。M2(5-8)->M3需等J1和J2?M3(8-10)->M1需等M1空闲?M1(10-13)3.J3:M3(0-2)->M