生产调度考试卷试题题库及答案

生产调度考试卷试题题库及答案一、单项选择题（本大题共20小题，每小题1分，共20分。在每小题给出的四个选项中，只有一项是符合题目要求的）1.在生产调度问题中，通常用“四参数表示法”α/β/A.机器环境B.作业特征和约束C.优化目标D.调度算法2.对于单机调度问题1|A.先到先服务（FCFS）B.最短加工时间优先（SPT）C.最早截止期优先（EDD）D.最长加工时间优先（LPT）3.Johnson法则主要用于解决（）调度问题，以最小化最大完工时间（Makespan）。A.单机B.并行机C.两台机器流水作业D.作业车间4.在流水车间调度中，若所有作业在所有机器上的加工顺序都相同，则称为（）。A.作业车间调度B.开放车间调度C.混合流水车间调度D.一般流水车间调度5.下列哪个指标属于衡量作业交货期的性能指标？（）A.最大完工时间()B.总完工时间(∑)C.最大延迟时间()D.总机器闲置时间6.对于1|A.SPT规则B.EDD规则C.Moore-Hodgson算法D.LPT规则7.在并行机调度问题中，若机器完全同构，且作业可在任何一台机器上加工，这属于（）。A.同型机B.同速机C.无关机D.专用机8.以下哪种启发式规则通常用于最小化最大完工时间的并行机调度？（）A.SPT规则B.LPT规则C.EDD规则D.FCFS规则9.在作业车间调度中，一个作业包含多个工序，这些工序（）。A.必须在不同机器上按特定顺序加工B.可以在任意机器上同时加工C.加工顺序可以随意改变D.只能在一台机器上完成10.调度问题中的“析取图”主要用于建模（）。A.流水车间调度B.作业车间调度C.单机调度D.并行机调度11.下列关于SPT规则的描述，错误的是（）。A.能最小化平均完工时间B.能最小化平均在制品库存C.在动态环境下通常表现优异D.总是能保证最大延迟时间最小12.对于n个作业、m台机器的流水车间调度问题，当m≥A.P类问题（多项式时间可解）B.NP-hard问题C.不可判定问题D.线性规划问题13.在考虑作业准备时间的调度中，若准备时间依赖于（），则问题变得更为复杂。A.机器状态B.作业顺序C.操作员技能D.环境温度14.Palmer算法是一种求解（）的启发式方法。A.单机调度B.流水车间调度（以最小化Makespan为目标）C.并行机调度D.项目调度15.下列哪种算法属于元启发式算法，常用于解决复杂的作业车间调度问题？（）A.Johnson法则B.分支定界法C.遗传算法D.动态规划法16.在生产调度中，“瓶颈资源”是指（）。A.加工能力最弱的资源B.加工成本最高的资源C.负荷率最高、限制系统产出的资源D.故障率最高的资源17.对于1|A.可以通过SPT规则在多项式时间内求解B.NP-hard问题C.只能通过枚举法求解D.无解问题18.在进行调度性能评估时，−表示作业j的（）。A.完工时间B.流程时间C.延迟量D.提前量19.“滚动窗口调度”技术主要用于解决（）环境下的调度问题。A.静态且确定B.动态且随机C.单件生产D.大批量生产20.下列哪个指标与总流程时间∑在数学上是等价的（假设所有作业同时到达）？（）A.总完工时间∑B.最大完工时间C.总延迟时间∑D.平均等待时间二、多项选择题（本大题共10小题，每小题2分，共20分。在每小题给出的四个选项中，有两项或两项以上是符合题目要求的）21.典型的生产调度问题目标函数包括（）。A.最小化最大完工时间()B.最小化总完工时间(∑)C.最小化最大延迟时间()D.最大化设备利用率22.下列哪些属于解决调度问题的精确算法？（）A.分支定界法B.动态规划法C.遗传算法D.模拟退火算法23.作业车间调度与流水车间调度的主要区别在于（）。A.作业车间中不同作业的加工路径可能不同B.流水车间中所有作业的加工路径相同C.作业车间允许工序有先后约束D.流水车间机器是并行的24.常见的调度优先级规则有（）。A.SPT(ShortestProcessingTime)B.EDD(EarliestDueDate)C.MWKR(MostWorkRemaining)D.FIFO(FirstInFirstOut)25.导致调度问题复杂性的因素包括（）。A.机器数量众多B.作业到达方式不同（静态vs动态）C.存在工序约束D.加工时间确定性26.下列关于遗传算法在调度中应用的描述，正确的有（）。A.需要设计编码方案来表示染色体B.交叉和变异是主要操作C.容易陷入局部最优D.属于精确算法，一定能找到全局最优解27.对于PmA.将作业按加工时间从大到小排序B.每次将作业分配给当前负载最小的机器C.性能上限比SPT规则好D.适用于单机调度28.生产调度的输入信息通常包括（）。A.作业数量及加工时间B.机器数量及可用性C.工艺路线（工序顺序）D.作业的交货期和优先级29.下列哪些情况会触发重调度？（）A.机器突发故障B.紧急订单插入C.原材料短缺D.加工时间估计错误30.在TOC（约束理论）中，DBR（Drum-Buffer-Rope）管理机制涉及（）。A.鼓：确定瓶颈资源的生产节拍B.缓冲：保护瓶颈资源不受干扰C.绳：控制物料投入时间D.池：增加非瓶颈资源的产能三、判断题（本大题共10小题，每小题1分，共10分。请判断正确或错误）31.对于单机调度问题，SPT规则不仅能最小化平均完工时间，也能最小化平均延迟时间。（）32.Johnson法则是解决两台机器流水车间调度问题以获取最小化最大完工时间的精确算法。（）33.所有的流水车间调度问题都是NP-hard问题。（）34.在并行机调度中，如果目标是最大化机器利用率，通常应尽量让机器满负荷运转，不考虑作业等待时间。（）35.EDD规则主要用于最小化最大误工时间。（）36.在作业车间调度中，只要总工时不变，机器的排列顺序对Makespan没有影响。（）37.模拟退火算法是一种基于蒙特卡洛方法的迭代寻优算法，理论上可以以概率1收敛到全局最优。（）38.静态调度假设所有作业在时刻0都已到达，且加工时间确定。（）39.关键路径是指在析取图中从起点到终点的最长路径，其长度决定了Makespan。（）40.提前期惩罚和延迟期惩罚在调度优化中通常被同等对待，无需区分。（）四、填空题（本大题共10小题，每小题2分，共20分。请将答案写在横线上）41.在调度问题表示法α/β/γ中，42.对于单机调度问题1|43.在并行机调度中，若各机器的加工速度不同，且作业j在机器i上的加工时间为=/44.考虑到作业的权重，最小化加权总完工时间1|45.在两台机器流水车间调度中，Johnson法则指出，若min(,)46.调度中的\_\_\_\_\_\_\_\_\_\_是指作业到达系统与开始加工之间的时间差。47.针对大规模调度问题，\_\_\_\_\_\_\_\_\_\_算法通过将问题分解为多个子问题（主问题和对偶问题）来求解，常用于整数规划模型。48.在蚁群算法中，蚂蚁在路径上留下的\_\_\_\_\_\_\_\_\_\_会随时间挥发，并随着后续蚂蚁经过而增强，用于指导搜索方向。49.\_\_\_\_\_\_\_\_\_\_调度是指将加工时间较长的作业优先安排，常用于并行机环境以平衡机器负荷。50.在柔性作业车间调度中，一个工序可以在\_\_\_\_\_\_\_\_\_\_台机器上加工。五、简答题（本大题共5小题，每小题6分，共30分）51.简述生产调度中SPT（最短加工时间优先）规则和EDD（最早截止期优先）规则的适用场景及其优缺点。52.请解释什么是“析取图”，并说明它在作业车间调度问题中的作用。53.简述Johnson法则解决两台机器流水车间调度问题的基本步骤。54.比较静态调度与动态调度的区别，并各举一个适用的生产环境例子。55.解释调度中的局部邻域搜索概念，列举至少三种常见的邻域结构（针对作业车间或流水车间）。六、计算题（本大题共3小题，共40分）56.（本题15分）设有5个作业，单机加工，其加工时间和交货期如下表所示：作业$j$12345加工时间$p_j$37452交货期$d_j$81510126(1)请使用SPT规则确定作业加工顺序，并计算该顺序下的最大完工时间和平均完工时间¯C。（5分）(2)请使用EDD规则确定作业加工顺序，并计算该顺序下的最大延迟量。（5分）(3)请使用Moore-Hodgson算法求解最小化误工作业数∑的最优调度序列，并给出最小误工作业数。（5分）57.（本题15分）某车间有两台机器和，有6个作业需经过这两台机器加工（流水作业，即先后）。各作业在机器上的加工时间如下表所示：作业$J_1$$J_2$$J_3$$J_4$$J_5$$J_6$$M_1$时间($a_i$)385629$M_2$时间($b_i$)546372(1)请利用Johnson法则求出最优加工顺序。（8分）(2)绘制该最优顺序下的甘特图，并计算最大完工时间（Makespan）。（7分）58.（本题10分）设有3台同型并行机器,,，现有7个作业等待加工，加工时间分别为：p(1)应用LPT（最长加工时间优先）列表调度算法，给出作业分配方案及各机器的完工时间。（5分）(2)计算该方案下的最大完工时间。（2分）(3)简述LPT算法在并行机调度中的主要思想。（3分）七、综合应用分析题（本大题共2小题，共30分）59.（本题15分）某柔性制造系统（FMS）包含三台机器：,,:(在上,4h),(在,上,3h),(在上,2h):(在,上,5h),(在上,4h):(在上,2h),(在,上,6h):(在上,3h),(在上,5h),(在上,3h)假设所有作业在t=(1)请构建该问题的析取图模型（描述节点、边及权重）。（5分）(2)这是一个典型的什么类型的调度问题？（3分）(3)若采用基于优先级规则的启发式算法进行调度，请设计一个简单的调度逻辑（例如：选择具有最多剩余工时的作业优先，工序选择加工时间最短的机器），并尝试推导一个可行的调度方案，计算其Makespan。（7分）60.（本题15分）在实际生产中，经常会遇到机器突发故障的情况，导致原定调度方案不可行。假设某车间正在执行一个生产计划，当前时刻t=10，机器突发故障，预计修复时间为5个时间单位（即t当前在机器队列中有以下待加工作业（已按原计划排序）：作业A:剩余加工时间3，需在上加工。作业B:剩余加工时间8，需在上加工。作业C:剩余加工时间4，需在上加工。同时，在t=12时，有一个紧急作业D到达，加工时间6，需在(1)分析在t=10时发生故障后，对作业(2)针对这种动态干扰，常见的重调度策略有哪些？请列举并说明。（6分）(3)结合上述案例，设计一种合理的重调度方案（考虑紧急作业D的插入），并给出在t=10参考答案与解析一、单项选择题1.A。解析：α/β/γ表示法中，α代表机器环境（如单机1、并行机Pm、流水车间Fm、作业车间Jm），β代表作业特征和约束（如释放时间、交货期），2.B。解析：对于1|3.C。解析：Johnson法则是专门针对两台机器流水车间调度问题（F24.D。解析：所有作业在所有机器上的加工顺序都相同，称为流水车间。若每台机器上作业顺序也相同，称为排列流水车间，但统称流水车间。5.C。解析：是最大延迟时间，直接反映了交货期的满足情况。和∑主要关注效率。6.B。解析：对于1|7.A。解析：并行机分为同型机（Identical，速度相同）、同速机（Uniform，速度不同但恒定）、无关机（Unrelated，速度依赖于作业）。题目描述的是同型机。8.B。解析：在并行机最小化Makespan问题中，LPT（LongestProcessingTime）规则通常比SPT表现更好，因为它倾向于先处理大任务以平衡负荷。9.A。解析：作业车间调度的定义是每个作业由一系列工序组成，这些工序必须在特定的机器上按预定的工艺路线加工。10.B。解析：析取图是作业车间调度的经典模型，节点代表工序，有向边代表同一作业的先后约束，无向边（析取边）代表同一机器上不同工序的互斥约束。11.D。解析：SPT最小化平均完工时间，但不保证最小化最大延迟时间。EDD才是最小化最大延迟的规则。12.B。解析：当机器数m≥3时，流水车间调度问题13.B。解析：依赖作业顺序的准备时间使得问题具有类似旅行商问题（TSP）的性质，增加了复杂性。14.B。解析：Palmer算法（基于斜度指数）是一种求解流水车间调度问题以最小化Makespan的启发式方法。15.C。解析：遗传算法、模拟退火、禁忌搜索等属于元启发式算法，适用于求解复杂的组合优化问题。16.C。解析：根据TOC理论，瓶颈是限制系统整体产出的资源，即负荷率最高的资源。17.B。解析：1||∑18.C。解析：=−19.B。解析：滚动窗口调度将时间轴分段，不断根据新信息重调度，适用于动态随机环境。20.A。解析：流程时间=−。若所有作业=0，则=，故二、多项选择题21.ABC。解析：设备利用率通常是衍生的指标，但直接优化的目标通常是时间相关的（A,B,C）。22.AB。解析：分支定界和动态规划是精确算法，能保证找到最优解。遗传算法和模拟退火是近似算法。23.AB。解析：流水车间路径相同，作业车间路径不同。两者都有工序约束。24.ABCD。解析：这些都是常见的优先级dispatchingrules。25.ABC。解析：加工时间确定是简化问题的因素，不确定性（如随机加工时间）才会增加复杂性。26.AB。解析：遗传算法是元启发式，容易陷入局部最优（虽然通过机制可以缓解），不是精确算法。27.AC。解析：LPT按大到小排序，通常性能比随机或SPT好，适用于并行机。28.ABCD。解析：这些都是调度模型必要的输入参数。29.ABCD。解析：机器故障、急单、缺料、数据误差都是动态环境下的典型干扰事件。30.ABC。解析：DBR包含鼓（瓶颈）、缓冲（保护瓶颈）、绳（投料控制）。池不是DBR的核心术语。三、判断题31.错误。解析：SPT最小化平均完工时间，但不保证最小化平均延迟时间，除非特殊条件。32.正确。解析：Johnson法则是F233.错误。解析：F2||34.错误。解析：调度通常需权衡效率与时间指标，盲目追求机器利用率可能导致大量在制品库存。35.错误。解析：EDD最小化最大延迟量。Moore-Hodgson算法用于最小化误工作业数∑。36.错误。解析：在作业车间中，机器排列顺序（即机器上的作业顺序）直接决定了Makespan。37.正确。解析：模拟退火具有概率突跳能力，理论上收敛于全局最优。38.正确。解析：静态调度的定义。39.正确。解析：关键路径决定了项目的总工期或调度的最大完工时间。40.错误。解析：通常JIT（准时制）模式下，提前和延迟都会受到惩罚，且权重可能不同。四、填空题41.释放时间（或到达时间）42.Moore-Hodgson（或最小化误工个数算法）43.同速机44.WSPT（加权最短加工时间优先）（即按/非减顺序）45.之前46.等待时间47.割平面48.信息素49.LPT（最长加工时间优先）50.多（或一或多）五、简答题51.答：SPT规则：适用场景：追求最小化平均完工时间、最小化平均在制品库存、提高系统通过率的场景。优点：计算简单，能有效缩短作业在系统中的平均停留时间，减少WIP。缺点：加工时间长的作业可能会长时间等待，导致最大延迟时间恶化，可能违反交货期。EDD规则：适用场景：关注交货期，希望最小化最大延迟时间的场景。优点：能保证最大延迟时间最小，较好地满足紧迫订单的需求。缺点：可能导致加工时间短的作业排在长作业后面等待，增加平均流程时间。52.答：析取图定义：是一个有向图G=(V,A,E作用：它将调度问题转化为图论问题。一个可行的调度方案对应于将析取边定向（确定同一机器上工序的加工顺序）后的无环图。调度的目标（如最小化Makespan）等价于在图中寻找一条从起点到终点的最长关键路径，并使其长度最小。53.答：Johnson法则步骤如下：1.将作业分为两组：集合包含所有在上加工时间小于等于在上加工时间的作业（即≤）；集合包含剩余作业（即>）。2.对中的作业，按（在上的时间）从小到大升序排列。3.对中的作业，按（在上的时间）从大到小降序排列。4.最优加工顺序为：的序列紧接着的序列。54.答：区别：静态调度：假设所有作业在开始时刻均已到达，且加工时间、机器数量等参数确定。一次性生成完整的调度计划，执行过程中不再改变。动态调度：作业陆续到达，加工时间可能随机，或机器可能发生故障。需根据实时状态不断调整或生成新计划。例子：静态调度：每天早班根据固定订单排产的机械加工车间。动态调度：根据临时客户订单随时调整插队的汽车维修厂，或处理随机故障的半导体生产线。55.答：局部邻域搜索：从一个初始解出发，在其邻域内寻找更优解，若找到则替换当前解，重复该过程直到满足终止条件。常见邻域结构：1.交换：交换解序列中两个不同位置作业的顺序。2.插入：将一个作业从当前位置取出，插入到另一个位置。3.逆序：将序列中两个位置之间的作业顺序反转。六、计算题56.解：(1)SPT规则：按加工时间排序：2(5顺序：→→完工时间：======¯(2)EDD规则：按交货期排序：6(5顺序：→→完工时间：=2,=5,=9,=14,=21,=(3)Moore-Hodgson算法(mi步骤：1.按EDD排序初始序列E:5(2.计算各位置完工时间：====143.在已排序列,,,中，移除加工时间最长的作业(p=5)。将其放入拒绝集R。E变为54.加入下一个作业。序列5,1=2=15,165.在,,,中移除最长作业(p=7)。放入R。E变为56.所有作业处理完毕。7.最终序列：E接R，即,,验证误工数：(2≤6),(5≤8误工作业数为2(,)。最小误工作业数∑=57.解：(1)Johnson法则求解：列表：:3,5:8,4:5,6:6,3:2,7:9,2按升序：(2),按降序：(4),最优顺序：→→(2)甘特图与Makespan计算：顺序：,时间数据：::::::计算完工时间：开始时间累加：((((((完工时间（需等待前道工序和本机前一作业）：((((((Makespan=35。58.解：(1)LPT列表调度算法：作业按降序排序：8,7初始机器负载==1.分配8：给。=8。2.分配7：给。=7。3.分配6：给。=6。4.分配5：最小负载为(6)，给。=5.分配4：最小负载为(7)，给。=6.分配3：最小负载为(8)，给。=7.分配2：最小负载为,,(均为11)，给。=11分配方案：:8,3,2(完工13):7,4(完工11):6,5(完工11)(2)=m(3)LPT思想：优先将加工时间长的作业分配给机器。这是因为长作业对最终完工时间的影响较大，若最后分配长作业，容易导致某台机器负载过重。先分配长作业有助于在初始阶段平衡各机器的负荷。七、综合应用分析题59.解：(1)析取图模型：节点V：包含虚拟起点S、终点T，以及各工序节点,,实线边A(ConjunctiveArcs)：表示作业内工序先后关系。SSSS虚线边E(DisjunctiveArcs)：表示机器能力约束。:与(若选)与(若选)与之间两两存在析取边。:(若选)与(若选)与与之间存在析取边。:(若选)与与(若选)与之间存在析取边。权重：节点权重（或边权重）为各工序的加工时间。(2)问题类型：这是一个柔性作业车间调度问题（FJSP）。因为工序可在多台机器上选择（机器柔性），且作业路径不同（作业车间特征）。(3)启发式调度方案推导：规则：MWKR（最多剩余工时优先）选择作业；工序选择最短加工时间机器。剩余工时计算：:4+3+2=9:5+4=9:2+6=8:3+5+3=11步骤：1.选(Max9->11)。工序(M1,3h)。安排[0-3]。2.剩余(9),(9),(83.剩余(9),(8)。选。工序(M1/M2,5h)。选M2(空闲)。安排4.剩余(8)。工序(M2,2h)。忙到5。安排[5-7]。5.更新剩余工时：(剩5),(剩4),(剩6),(剩8)。选。工序(M2,5h)。