CAJ | 학술논문

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下，使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型，提出了基于图着色模型的启发式算法进行求解。首先，使用冲突图来描述货物之间的冲突关系；其次，基于冲突图，采取图着色的方式将货物进行分组，并且组内的货物之间不存在冲突关系；最后，采取改进FFD算法对每组的货物进行装箱操作。实验表明，本文提出的启发式算法能够快速有效地找到问题的可行解，为此类装箱问题的求解提供了新思路。
대유충돌관계장상문제적우화목표시재만족화물충돌관계적전제하，사용수량최소적화상완성화물장상적목적。본문분석료충돌장상문제적수학모형，제출료기우도착색모형적계발식산법진행구해。수선，사용충돌도래묘술화물지간적충돌관계；기차，기우충돌도，채취도착색적방식장화물진행분조，병차조내적화물지간불존재충돌관계；최후，채취개진FFD산법대매조적화물진행장상조작。실험표명，본문제출적계발식산법능구쾌속유효지조도문제적가행해，위차류장상문제적구해제공료신사로。
The objection of bin packing problem with conflicts (BPPC)is to minimize the number of bins used to accommodate all the items , and also has to satisfy the conflict constraints among the items .This paper summaries the mathematical model of BPPC , and proposes a heuristic algorithm based on graph coloring model to solve it . Firstly, a conflict graph structure is used to represent the conflict relationship among the items , and then, based on the conflict graph , the algorithm will finish a coloring procedure to group all the items and ensure that there is no items with conflict relationship in each group , and lastly , an improved FFD algorithm is used to complete the packing operation for the items in each group .The experiments show that the algorithm of this paper could find a feasible solution of BPPC quickly and efficiently , and provide a new approach for this kind of bin packing problems .