论文部分内容阅读
n个工件要在一台有高度限制的批处理机上分批进行加工,工件j的加工时间和高度分别为pj和sj,批的加工时间为批中加工时间最大的工件的加工时间,每批加工时,机器的剩余量为批处理机的高度与批中工件的高度和之差,目标函数最小化机器空余总量和工件总完成时间,该NP-难问题源于钢铁企业的罩式退火炉调度问题。基于部分工件分批性质,提出贪婪算法;提出工件SPT顺序的最优分批-动态规划算法,并对两种算法进行了比较。为了进一步检验算法,把动态规划算法应用于总完成时间最小化问题,与已有算法进行了比较;根据相邻批的工件加工时间的取值,提出分批修改规则,并与动态规划结合实现局域搜索算法(DPLS),通过仿真实验表明DPLS算法非常有效。
n pieces of work to a batch of machines with a high limit batch processing, the processing time and height of the workpiece j, respectively, pj and sj, batch processing time for the batch processing time of the largest processing time of the workpiece, each batch During processing, the remaining amount of the machine is the difference between the height of the batch machine and the height of the workpiece in the batch. The objective function minimizes the total amount of the machine empty and the total finished time of the workpiece. The NP- Furnace scheduling problem. A greedy algorithm is proposed based on the batched nature of some workpieces. An optimal batching-dynamic programming algorithm for workpiece SPT sequence is proposed. The two algorithms are compared. In order to further test the algorithm, the dynamic programming algorithm is applied to the problem of minimizing the total completion time and compared with the existing algorithms. According to the value of the workpiece processing time of adjacent batches, a batch modification rule is proposed and combined with the dynamic programming Local Search Algorithm (DPLS), through the simulation experiments show DPLS algorithm is very effective.