多资源多工序生产调度的状态模型

多资源多工序生产调度的状态模型第1页多资源多工序生产调度的状态模型作者：王小川周枫庄莉摘要本文讨论了多资源、多工序，工序无次序性条件下的生产调度模型。模型以调度方案——生产状态序列为求解目标，通过建立基本的状态约束等式，将不同条件下的生产调度要求统一到同一模型中，用同一算法进行求解。各问题间的区别仅在于状态集合的求解和资源约束不同。问题一要求无资源浪费，我们给出了手工计算的方法及其理论证明；问题二要求减小规模，且无资源浪费，我们的程序可以判断不同规模下是否能够进行无资源浪费生产，如果能，则可以给出用“Gantt图”或“二维资源调度方块图”表示的调度方案；针对问题三要求浪费最小的特点，我们引入“统一资源函数”，使得统一描绘五种资源的利用、浪费状况成为可能，大大减小计算量，给出了比问题中要求的更好的解。另外，还讨论了使生产周期最小和生产规模最小的方案，以及它们之间的关系。一.问题重述图1是某企业的生产结构示意图，A0是出厂产品，A1，…A6是中间产品，图中Ai→Aj表示生产一个单位Aj需要消耗K单位Ai，其余类似。表1给出了生产单位产品所需的资源（工人，设备）和时间，注意，表中所给的数据是基本的。即，既不能通过增加工人和设备来缩短时间，也不能通过加长时间而节省工人和设备。问题1：无资源浪费、连续均衡生产的最小生产规模是多大？相应的最短周期是多少？其中“无资源浪费”指的是整个生产周期中没有闲置的设备和闲散人员。“连续”指整个周期中所有产品生产过程不会停顿。“均衡”指所有中间产品A1，…A6和库存与上一周期结束时的库存相同。“生产规模”指完成整个生产过程所需各资源的总和。问题2：如果考虑相同的资源可以通用，那么问题1得到的最小生产规模在无资源浪费、均衡生产中能否减少。请写出你得到的生产规模，相应的周期和生产过程的调度方案。问题3：如果该企业的资源限制为：I类工人120名，Ⅱ类工人80名，技术人员25名，甲种设备8台，乙种设备10台，及周期限制（一星期，共24╳5.5=132小时）。请你作出生产过程的调度方案，使在均衡生产条件下资源的浪费最小。表1生产单位产品所需资源和时间产品A0A1A2A3A4A5A6I类工人71273437183317Ⅱ类工人30181713122823技术人员79076511甲种设备4304202需要的资源乙种设备1310256加工时间6365212多资源多工序生产调度的状态模型第2页二.问题分析在实际生产中，资源的合理安排和调度将使生产过程达到最优。在连续批量生产中，同一批人员和设备在一个生产周期往往从事同一种产品的生产。而单位成品所需各种中间产品的数量有确定的比例关系。所以，需要合理分配投入到各种产品生产中的人力、物力等多种资源，使中间产品以合适的比例进行生产，生产和消耗达到均衡，避免某种产品库存的空缺或积压。在各种生产要素（所需资源和生产时间）确定的情况下，这种以“专物专用”为特征的连续批量生产的最小生产规模是确定的（这在下文中将有详细讨论）。实际上，许多同类资源在生产中可以通用，即，同一资源可以用于多种产品的生产，同一批资源（人力、设备）在单位生产周期不同时间段可以从事不同产品的生产。在保证产品按比例、均衡生产的前提下，对各种资源进行合理搭配，可以大大减小生产规模。由于客观限制，能提供的资源是给定的，周期也一定。这种情况下，在该确定周期下生产的产品越多，将使资源浪费越少。三.基本定义资源：是与生产相关的设备和人员的总称。称1类工人为第1种资源，2类工人为第2种资源，…，乙种设备为第5种资源。工序：指生产一个特定产品的过程。每个工序有生产的起始时刻和结束时刻，两者差值为该工序的加工时间。有７种不同类别的工序，分别对应生产产品A0，A1…A6，分别称为第０种工序，…，第６种工序。显然，同种工序的加工相同的产品,所需时间和资源相同。包含关系“≥”：对同维数的向量（或矩阵）ａ和ｂ，若有ａ≥ｂ，则表示ａ的各分量不小于ｂ的各分量。同理定义被包含关系“≤”。若ａ≤O，则表示a的各分量小于等于0。包含关系（被包含关系）是偏序关系。A0A4A1A5A2A3A62154331多资源多工序生产调度的状态模型第3页四.基本假设I.每种产品都有足够用以保证下一步生产顺利进行的库存量。这样，各种工序可以独立进行，不需要等待前级中间产品的完成。II.每个工序是一个不可打断的基本生产过程。III.可以同时生产多个同一种产品，即允许多个同种工序同时开工。对同时开工的同种工序等同对待，不加区别。IV.由于各工序所需时间均为整数。在整个讨论中，时间变化的最小单位是小时。V.一个周期可以完全独立。没有任何一个工序跨在两个整体周期之间。VI.一个周期中生产出的最终产品所消耗的中间产品可由该时间段内的中间产品的生产得到完全、恰好的补充。即，生产是均衡的，产品的生产按组装要求成比例进行，一个周期结束时各中间产品（A0,A1,A2,A3,A4,A5,A6）的库存与上一周期相同。VII.假设所有资源和工序在生产过程中一切正常，不考虑偶然事故的发生。五.基本符号和术语约定在建模中使用的各种符号及有关术语说明如下：T：生产周期。A：工序－资源需求矩阵。6,,1,0,5,2,1,][75LL===×jiaAij其中ija表示第j种工序所需的第i种资源的数量。uT：工序所需时间。[]TuuuuuuuutttttttT6543210=其中)6,5,4,3,2,1,0=jtuj（表示生产一个最终产品所需第j种工序的总加工工时。n：一个周期内生产最终产品的数目。M：工序需求比例。[]TmmmmmmmM6543210=其中)6,5,4,3,2,110==jmmj（，表示生产一个成品A0所需第j种工序的数量。W：单位成品蕴含的劳动量。[]T=其中5,4,3,2,1=iwi，表示生产单位成品（包括最终产品和相应中间产品）所需第i种资源的总工时（台·时或人·时）。tN：单位成品蕴含的工序时间量。[]TttttttttnnnnnnnN6543210=其中)6,5,4,3,2,1,0=jntj（表示生产单位成品所需第j种工序的总加工时间。多资源多工序生产调度的状态模型第4页mR：资源规模。即，在整个生产周期中各种资源的曾达到的最大资源使用量。[]TmmmmmmrrrrrR54321=其中，)5,4,3,2,1(=irmi表示在整个生产过程中第i种资源的最大使用量。lR：资源限制。[]TllllllrrrrrR54321=其中，)5,4,3,2,1(=irli表示在整个生产过程中第i种资源的最大允许使用量。我们下面还将随着模型建立进一步引入有关符号和名词。文中还将不加说明的引用这些符号的变形、在计算中引入相应表示符号，这些将从上下文中容易得到其具体含义。六.模型建立(一).生产状态、资源使用描述量的引入。由基本假设IV，任何工序的开工和结束都定在整时刻上，因而在时间段［ｔ，ｔ＋１）内，生产的状态不发生改变，即，时间段［ｔ，ｔ＋１）内的生产状态同时刻ｔ的生产状态相同。再由基本假设Ⅲ，对某一时刻，只讨论不同种工序开工的数量，正在进行的同种工序不加区别。定义如下函数反映任何时刻的生产状态：)(tX：时刻ｔ进行的工序。[]TtxtxtxtxtxtxtxtX)()()()()()()()(6543210=其中6,5,4,3,2,1,0),(=jtxj表示时刻t正在进行的第j种工序的数目。)(tS：时刻ｔ新开工的工序。[]TtstststststststS)()()()()()()()(6543210=其中6,5,4,3,2,1,0),(=jtsj表示时刻t新开工的第j种工序的数目。)(tF：时刻ｔ结束的工序。[]TtftftftftftftftF)()()()()()()()(6543210=其中6,5,4,3,2,1,0),(=jtfj表示时刻t结束的第j种工序至此，从函数)(tX，)(tS和)(tF，我们已经可以完全描述某一时刻生产状况和该时多资源多工序生产调度的状态模型第5页刻生产状态变化的情况。满足特定生产条件的所有可能生产状态X的集合称为状态集，记作XS。对)(),,0[tXTt∈∀都是状态集XS中的元素。（在下文中将有更进一步的说明）。对于资源使用情况我们引入资源使用状态量R(t)，表示时刻t各种资源的使用量。[]TtrtrtrtrtrtrtrtR)()()()()()()()(6543210=其中6,5,4,3,2,1,0),(=jtrj表示时刻t第j种资源正在投入使用的数量。(二).生产及其调度的模型描述1．基本生产模型时刻ｔ－1进行的工序为X(t-1)，在时刻ｔ时结束的工序为F(t)，由基本假设Ⅱ（工序不可打断），时刻ｔ将继续进行时刻ｔ－1未完成的工序为)()1(tFtX−−。下一时刻进行的各种工序的数目将不小于前一时刻未完成的工序数目。即有：(其中“≥”为前文定义过的包含关系，下同)X(t)≥X(t-1)－F(t)）公式1.6(LLLLLLLLL时刻ｔ新开工的工序为：S(t)＝X(t)－[X(t-1)－F(t)])2.6(公式LLLLLLLLL再由基本假设Ⅱ，时刻t结束的第j种工序必在时刻t–tuj开始。故有：[]TtftftftftftftftF)()()()()()()()(6543210=，其中6,5,4,3,2,1,0),()(=−=jttstfujjj)3.6(公式LLLLLLLLL任何一种可能的生产过程都有唯一对应的X(t)，F(t)，S(t)函数，且X(t)，F(t)和S(t)满足上述三个公式。而满足上述三个基本公式的X(t)，F(t)和S(t)则对应一种可能存在的生产过程。而且，由（公式6.2）、（公式6.3），可根据X(t)确定唯一的S(t)和F(t)。（公式6.1）则反映了基本假设Ⅱ的要求：没有完成的工序不可以中间停止。可见，构造出合理的X(t)，t∈[0，T），这就对应一个可能的生产过程。我们就能将之表述为一种合理的调度方案。在下面的讨论中，我们将根据具体的条件和要求，限制或扩展这个模型，求解X（t）并将之表述为调度方案。2．生产状态与周期的关系若连续生产过程存在周期T，则X(t)=X(t+T)。可得到S(t)=S(t+T)，F(t)=F(t+T)。不妨设一个整周期为〔０，T）。由假设VI，没有跨周期的工序，则X(0)＝S(0)，X(T-1)＝F(T)。即，可将X(t)完全独立出来，限制在一个周期里考虑。即对X（t）限制如下：多资源多工序生产调度的状态模型第6页≥≤=)(0)0()()0(0)(TtTttXttX不变原）公式4.6(LLLLLLLLL构造出X(t)后再以Ｔ为周期延拓，即得整个时间轴上的生产模型。3．生产状态与资源使用的关系每一时刻的资源使用量由每一时刻的生产状况唯一决定。由此，我们得到“生产状态—资源使用基本等式”。其中)(txajij表示了t时刻生产第j种产品使用的第i种资源的量。===∑∑∑∑∑=====60560460360260154321)()()()()()()()()()()()(jjjjjjjjjjjjjjjtxatxatxatxatxatAXtrtrtrtrtrtR）公式5.6(LLLLLLLLL在不同生产要求下，满足该公式的所有)(tX的集合，我们称之为状态集XS。4．生产、资源与产品的关系一个周期内所有投入生产的实际资源，在一个周期结束使都等价得到一定数量的最终产品。我们有如下“资源投入—产出基本等式”：WntrtrtrtrtrtRTtTtTtTtTtTt==∑∑∑∑∑∑−=−=−=−=−=−=10510410310210110)()()()()()(）公式6.6(LLLLLLLLL一个周期中开工或结束的各种工序的和，在周期结束时都等价得到所生产的各种产品的个数。又由基本假设VI，有∑∑−=−===1010)()(