机械加工中资源约束问题的研究

Research of the problem of the resources optimize in machining

具有资源约束的调度问题在实际的机械加工中具有很强的应用背景。这里讨论一类工件间具有平行链优先约束的单机调度问题,同时工件的加工时间受资源约束,目标函数在满足资源消耗总量限制条件下,极小化加权总完工时间。研究考虑了两种情况,即一种是中链不允许中断,给出了多项式时间的算法;另一种是中链允许中断,引入了关键工件和优先因子的概念。证明了首先选择优先因子最小的链,连续加工直至关键工件完工产生的调度为最优调度,同样对该种情况给出了多项式时间的算法,并引入数值算例,对算法的运行过程进行了说明,验证了算法的有效性。

A class of single machine scheduling problem with chains constrains is investigated. In this model,it is assumed that the processing times of the jobs are subject to resource constrains. Many machine design and manufacturing process can be described by this kind of scheduling model. The objective is total weighted completion times. Two versions of problem are addressed. In the first one the chains can＇t be interrupted,whereas in the second one the chains can be interrupted. For both cases ,polynomial algo-rithms are presented,respectively. The definitions of key jobs and precedence factor are given for the second kind of problem. We also give an example to illustrate the feasibility of the algorithm.