Many interesting problems in computer systems, operations research, and production systems are transformed into rectangle packing problems known as bin packing problems. Provided that a list of rectangles and a rectangular space called a bin are given, the objective of the bin packing problem is to minimize the total height of the packing. As an optimization problem over geometric objects, the bin packing problem assumes strict satisfaction of constraints. In real world situations, however, a certain level of inaccuracy or violation among constraints is usually permitted because estimation is uncertain and some constraints do not need to be satisfied strictly. This thesis proposes a formulation of the bin packing problem based on the fuzzy set theory, named as the fuzzy bin packing problem. The problem is defined as a fuzzy optimization problem, which maximizes the user's satisfaction level, which is defined in terms of fuzzy sets. The fuzzy bin packing problem uses fuzzy sets for representing the widths and heights of the rectangles. The boundaries of the bin are also represented by fuzzy sets. The objective of the fuzzy bin packing problem is to maximize the satisfaction level, which compromises the packing height with the violations among constraints. Heuristics for finding feasible solutions are also proposed. These heuristics search for the lowest and leftmost positions which do not decrease the total satisfaction when the given piece is placed. An application to an industrial scheduling problem, called nozzle allocation scheduling problem, is presented as an illustration of the usefulness of the proposed problem and related algorithms.
빈패킹이라고 알려진 사각형 쌓기 문제는 컴퓨터 시스템이나 생산 시스템, 혹은 업무 생산성 향상 연구등에서 발생하는 여러가지 흥미로운 문제들을 해결하는데 도움을 준다. 빈패킹 문제는 몇개의 사각형 개체들과 빈이라고 불리는 사각형의 공간이 주어져 있을 때 전체 높이를 최소화 시키는 방향으로 주어진 사각형들을 쌓아넣는 것을 목표로 하는 문제이다. 이 문제는 기하학적인 개체들을 최적의 상태로 배치하는 문제의 일종이다. 따라서 주어진 제약조건들이 매우 엄격하게 만족된다고 가정한다. 반면에 실제 상황에서는 어느정도 수준의 부정확성이나 제약조건간의 절충등이 허용된다. 왜냐하면 예측값이 부정확할 수도 있고 어떤 제약조건들은 굳이 엄격하게 적용할 필요가 없을 수도 있기 때문이다. 따라서 이 논문은 퍼지 집합론에 기초한 빈패킹 문제를 제안한다. 이 논문에서 퍼지 빈패킹이라고 불리게 되는 이 문제는 일종의 퍼지 최적화 문제이며 퍼지 집합으로 정의된 사용자의 만족도를 극대화시키는 문제로 정의된다. 퍼지 빈패킹 문제에서는 사각형의 폭과 높이를 나타내는데 퍼지 집합을 사용하고 사각형 공간의 경계영역도 역시 퍼지 집합으로 정의한다. 퍼지 빈패킹 문제의 목표는 쌓아넣은 높이와 제약조건들을 절충하여 만족도를 극대화 시키는 해를 찾는 것으로 이 해를 찾기위한 휴리스틱 알고리즘들도 이 논문에서 제안된다. 제안된 휴리스틱들은 될수 있는 한 낮고 왼쪽으로 치우친 지점에 퍼지 집합으로 표현된 사각형 조각을 위치시키는 전략을 사용한다. 이 때 되도록이면 만족도를 감소시키지 않도록 여러가지 휴리스틱을 사용한다. 제안된 문제의 유용성을 보여주는 응용예로써 노즐 할당 문제를 설명하고 제안된 문제와 휴리스틱을 적용한 예를 보인다.
