2007年12月 机械科学与技术 December 2007 第26卷第12期 Mechanical Science and Technology for Aerospace Engineering Vol.26 No.12 基于MCMC方法的随机加工时间研究 于晓义，褚崴，孙树栋 (西北工业大学机电学院，西安710072) 于晓义 摘要：在分析随机作业调度问题特点的基础上，建立了随机加工时间统计模型及参数估计模型， 在参数未知及参数已知的条件下，提出了基于马尔可夫链蒙特卡罗方法的随机加工时间统计技术， 并通过吉布斯抽样实现了加工时间的参数估计。通过计算机仿真实验，验证了该方法的可行性及 有效性，为随机作业调度提供更特合实际生产的数据支撑。 关键词：随机作业调度问题；随机加工时间；马尔可夫链蒙特卡罗方法；吉布斯抽样 中图分类号：TP272 文献标识码：A 文章编号：10038728(2007)12-1574-04 Study of Stochastic Processing Time Using MCMC Method Yu Xiaoyi,Chu Wei,Sun Shudong (School of Mechatronics,Northwestem Polytechnical University,Xi'an 710072) Abstract:After analyzing the characteristics of stochastic job-shop scheduling problem,we establish the stochastic processing time statistics model and the parameter estimation model.Under the two conditions that there may exist known or unknown parameters,we propose our stochastic processing time statistics technique based on the Markov chain and the Monte Carlo (MCMC)method.Then we do the Gibbs sampling to estimate the unknown parameters of stochastic processing time.Finally,we carry out the simulation of the technique,and the simulation results veri- fy its feasibility and effectiveness. Key words:stochastic job shop scheduling probelm;stochastic processing time;Markov Chain and Monte Carlo (MCMC)method;Gibbs sampling Job-shop优化调度问题已经成为提高企业生产求。随机加工时间的确定成为随机作业调度的瓶颈 效率的核心问题。工序加工时间是job-shop优化调 问题，因此迫切需要一种对随机加工时间进行准确 度的关键数据。传统的车间作业调度都是依事先确 估计的方法。由于实际可测工序加工时间通常包含 定的加工时间（常值）进行生产作业调度，而在生产 了生产过程中的各种扰动（如机器性能影响因素、 实践中，加工时间往往是随机变化的，传统的方法已 加工班组的影响因素等)，不能直接获得工序的加 不能满足现代企业车间作业调度的需求。考虑随机 工时间。本文提出了一个基于马尔可夫链蒙特卡罗 加工时间的调度问题具有重要意义，随之出现了随 方法的随机加工时间估计方法。 机作业调度的研究1，。然而，在现有的随机作业 调度研究中许多研究者都集中在对随机作业调度算 1问题建模 法的研究上，而对作为随机作业调度的主要数据支1.1随机加工时间问题建模 撵一随机加工时间的研究比较鲜见。上述研究中 以确定工件的某道工序作为描述对象。生产过 的随机加工时间都是通过从假设服从均匀分布的某 程中可测的工序生产周期包含了工件的加工时间、 一范围中取随机数来获得，而且对于其具体的取值 生产过程干扰因素（加工班组的技术因素、操作者 区间亦未作明确的阐述。笔者认为无论随机作业调 的生理因素、设备的不稳定因素等)影响产生的时 度算法效率及性能的高低，如果没有准确的加工时 间偏移。假设： 间数据，其调度方案都不能符合实际的生产调度要 (1)工序加工时间是独立的随机变量 收稿日期：2006-11-13 基金项目：国家863计划项目(2001AA412150,2003A4411110)和教育部博士点基金项目(2004699025)资助 作者简介：于晓义(1980-)，男（汉），山东，博士研究生，uxioi@mil.pu.cd血.cm 万方数据2007年 第26卷 12月 第12期 机械科学与技术 MeclIanical Science肌d TeclIIIology for AeD∞pace Engin∞ring D∞ember 200r7 V01．26 No．12 于晓义 基于MCMC方法的随机加工时间研究 于晓义，褚崴，孙树栋 (西北工业大学机电学院，西安7100r72) 摘要：在分析随机作业调度问题特点的基础上，建立了随机加工时间统计模型及参数估计模型， 在参数未知及参数已知的条件下，提出了基于马尔可夫链蒙特卡罗方法的随机加工时间统计技术， 并通过吉布斯抽样实现了加工时间的参数估计。通过计算机仿真实验，验证了该方法的可行性及 有效性，为随机作业调度提供更符合实际生产的数据支撑。 关键词：随机作业调度问题；随机加工时间；马尔可夫链蒙特卡罗方法；吉布斯抽样 中图分类号：吼72 文献标识码：A 文章编号：1003名728(2007)12·1574讲 Study of Stochastic Processing Time Using MCMC Method Yu Xiaoyi．Chu Wei。Sun Shudong (Sch00l 0f M∞lIa_嘶IIi∞，Nortllwe8tem Pol”echrIical UIlive玛畸，)【i’肌7100r72) AbSt船ct：触er analy菌ng dle ch眦cteristics of stoch鼬tic job—Shop∞heduling problem，we establish tlle 8tcIch鹊tic pmce鼹ing dme 8tatistic8 mDdel and tlle pammeter estimati∞model．Under出e two c仰ditio璐tllat tlle陀may眈ist lcIlown or unkIlo、^rIl p盯眦eters，we prop0∞ollr stoch鹪tic processing time 8tatistics technique b船ed∞吐Ie Markov chain肌d tlIe Monte Callo(MCMC)metllod．nen we do tlle Gibbs sampling to esti眦te出e吼kIlowIl p蹦珊ete玛 0f 8toch酗tic processing time．Finally，we c邺7 out tlle siInulation of山e tecllIlique，and tlle 8imulation托叭lts Veri一 匆its fe黯ibility明d ef＆ctiveness． 15【ey words：stochastic job shop scheduling pIobehn；stochastic pI．ocessing time；MarkoV Chain肌d MoIIte Carl0 (MCMC)method；Gibbs s锄pling Job一8hop优化调度问题已经成为提高企业生产 效率的核心问题。工序加工时间是job-shop优化调 度的关键数据。传统的车间作业调度都是依事先确 定的加工时间(常值)进行生产作业调度，而在生产 实践中，加工时间往往是随机变化的，传统的方法已 不能满足现代企业车间作业调度的需求二考虑随机 加工时间的调度问题具有重要意义，随之出现了随 机作业调度的研究H．9】。然而，在现有的随机作业 调度研究中许多研究者都集中在对随机作业调度算 法的研究上，而对作为随机作业调度的主要数据支 撑——随机加工时间的研究比较鲜见。上述研究中 的随机加工时间都是通过从假设服从均匀分布的某 一范围中取随机数来获得，而且对于其具体的取值 区间亦未作明确的阐述。笔者认为无论随机作业调 度算法效率及性能的高低，如果没有准确的加工时 间数据，其调度方案都不能符合实际的生产调度要 求。随机加工时间的确定成为随机作业调度的瓶颈 问题，因此迫切需要一种对随机加工时间进行准确 估计的方法。由于实际可测工序加工时间通常包含 了生产过程中的各种扰动(如机器性能影响因素、 加工班组的影响因素等)，不能直接获得工序的加 工时间。本文提出了一个基于马尔可夫链蒙特卡罗 方法的随机加工时间估计方法。 l问题建模 1．1随机加工时间问题建模 以确定工件的某道工序作为描述对象。生产过 程中可测的工序生产周期包含了工件的加工时间、 生产过程干扰因素(加工班组的技术因素、操作者 的生理因素、设备的不稳定因素等)影响产生的时 间偏移。假设： (1)工序加工时间是独立的随机变量 收稿日期：2006—1l—13 基金项目：国家863计划项目(2001AA412150，2003从411110)和教育部博士点基金项目(2004699025)资助 作者简介：于晓义(1980一)，男(汉)，山东，博士研究生，”xiaoyi@mail．nWpu．edu．∞ 万方数据