CAJ | 학술논문

讨论了双目标甬数下需要安装时问的平行多功能机排序问题.在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数.根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP-难的.设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组.从而得到一系列的启发式有效解.实验表明,该算法是实用而有效的.
토론료쌍목표용수하수요안장시문적평행다공능궤배서문제.재해문제중,매개공건대응궤기집합적일개자집,차매개공건지능재상응자집중적임일태궤기상가공,공건분조,불동조중적공건련속가공수요안장시간,목표함수위겁소화최대완공시간화안장차수.근거실제응용배경학정쌍목표배서문제적형식,병증명료해문제시NP-난적.설계료일개구계발식유효해적산법,수선안조특정적규칙장소유공건조도정조지안배도각태궤기상,연후축보개진최대완공시간화탁분공건조.종이득도일계렬적계발식유효해.실험표명,해산법시실용이유효적.
A multi-purpose machine scheduling problem with bicriteria and setup times is discussed.In which jobs can be processed by any machine of a prespecified subset of the machine set,moreover,jobs are divided into different groups and a changeover time is required whenever there is a switch from processing a job of one group to another job of a different group.Objective function of this problem is to minimize makespan and total times of setup.Style of the bicriteria scheduling problem is established according to the background of practical application.As the problem is proved to be NP-hard,a heuristic which provides heuristic efficient solutions is presented.In the heuristic,dispatch all the job groups to machines according to specific rules firstly,then a series of heuristic efficient solutions can be achieved by improving the makespan and splitting the job groups gradually.Extensive computational experiments indicates the feasibility and effectiveness of this heuristic algorithm.