差异尺寸不相容工件族批处理机调度问题研究

Batch processing machine scheduling is an important extension of classic scheduling problems. The basic hypothesis is to process several jobs simultaneously as a batch. The problems of scheduling batch processing machines are wildly encountered in the field of manufacturing like semiconductor manufacturing, steel casting, material handling, aircraft industries etc.. The effect of job families has to be considered in batching when different processing recipes are required.An extensive study of scheduling batch processing machines with incompatible job families is to be conducted in the research in which jobs with non-identical sizes and processing times are considered. New constraints are introduced when jobs belong to incompatible job families and the problem of scheduling batch processing machines is more complex and more applicable. The problem under study is NP-hard, thus on one hand, solution algorithms are designed for analysis and solve the problem in a reasonable time. On another hand, optimization models considering various objectives and machine environment are studied base on proper hypothesises and the solutions are generated by using algorithms designed. Further research ideas and help for manufacturing can be provided through this research.

批处理机调度问题是经典调度问题的一类重要扩展，其基本假设是机器可以对多个工件同时进行处理。在生产制造领域，批处理机具有广泛的应用，如半导体集成电路制造、钢铁铸造、物料搬运、航空工业等。当产品加工过程涉及不同工艺方案时，在其成批过程就需要考虑工件族的影响。本项目即对工件属于不相容工件族的批处理机调度问题做进一步研究，并考虑工件具有差异尺寸以及不同加工时间的情况。当工件分属于不相容工件族时，工件成批的过程会产生新的约束，批处理机调度问题变得更为复杂，也更贴近实际生产环境。由于该类问题是NP-难的，因此本项目一方面对其求解算法进行设计，以平衡求解的时间和解的质量；另一方面，通过合理假设，研究在不同优化目标以及机器环境下模型的建立，并结合所设计算法对问题进行仿真求解。通过对该类批处理机调度问题进行研究，可为调度问题的研究提供新的思路，并为实际生产提供借鉴。

本项目对生产调度领域中的一类批处理机调度问题进行研究。该类问题在生产实践中具有广泛的应用，相对于经典调度问题，该类问题更为复杂，也更易成为生产过程的瓶颈环节。对这类问题进行研究将有效提高企业生产效率，降低成本。.本项目的主要研究内容从机器环境、加工特征、优化目标等方面逐步深入。在机器环境方面，以单机为基础，扩展到多机环境；在加工特性上考虑了工件从属于多个不相容工件族的这一类典型特性；在优化目标上从单目标扩展到了多目标。研究主要结果如下：.（1）考虑了工件尺寸相同的情况，对工件成批算法进行了优化设计，给出FFLPTD和BFLPTD算法。结合枚举机制提高算法的解空间搜索能力，有效提高了解的质量。.（2）考虑不相容工件族的Lmax优化问题，建立了该问题的数学规划模型，设计了下界算法以及成批数量的上界算法。设计了启发式算法以及改进启发式算法对问题进行求解。.（3）对同时考虑制造跨度和电力成本的多目标类批处理机调度问题进行研究，建立多目标数学优化模型。基于批序和工件序提出两种蚁群算法对该问题进行求解。.（4）针对批处理机调度问题，设计了MMAS算法，定义信息素、启发式信息以及解的构造过程，并设计了局部优化算法对其进行改善。.本项目对批处理机调度问题以及考虑不相容工件族的批调度问题进行了建模、算法设计和评价，为该类问题的求解提供了有效的启发式算法。所设计模型及算法对该领域的研究提供了较好的理论基础，也对生产实践也提供了方法参考，具有较好的理论及实践意义。