【作者】 计哲飞；

【导师】 邢文训；

【作者基本信息】 清华大学 ， 数学， 2009， 硕士

【摘要】 排序问题,即在一定条件下,寻找给定工件在一台或多台机器上安排加工的时间表,使其满足一定需要。本文以钢铁企业生产中的炉机匹配问题为背景,研究了一类特殊的柔性流水作业排序问题:工件需要在炼钢炉和铸机上顺序加工,在加工过程中工件不允许等待,并且在第二个阶段,铸机的生产不能中断。本文首先证明了2台炼钢炉以上的炉机匹配可行解判定问题为强NP-hard,然后根据实际背景对工件的加工时间做了进一步限制,在证明目标函数为最大完工时间的情况下问题复杂性为NP-hard后,给出了启发式算法BMLPT,对该算法进行了界估计,并通过模拟计算与已有算法MLPT进行比较。更多还原

【Abstract】 Scheduling is a form of decision making to find a schedule for a set of jobs on some machines under certain conditions. This paper considers a two-stage flexible flow shop scheduling problem arisen from steel and iron production, where no wait between two sequential operations of a job is allowed and there is no idle time between two consecutive processed jobs on machines of the second stage.In this paper, firstly we prove that verifying the existence of a feasible scheduling is strong NP-hard for more than two machines in the first stage. Based on some further restrictions on the processing time according to the actual background, we show its complexity and present a heuristic algorithm BMLPT with asymptotically error bounds. Furthermore, BMLPT and MLPT are compared by computer simulation.更多还原