顏色數量限制下之印刷排程

Abstract

本論文探討顏色數量限制下的印刷排程問題，著重在研究可重疊背包問題的解法。此類型的題目中，每筆訂單包含多個顏色需求，目標為找到一個集合擁有最多的印刷件數，其中所使用的印刷顏色不超過所規範之個數，但滿足集合中所有訂單。

在論文中，我們採用整數規劃描述問題並求得最佳解，另外亦設計模擬退火演算法求得近似解，並比較兩者的求解效率與品質。在實驗中，我們比較各個參數對本題目最佳解的影響，以及模擬退火演算法在本題目應用的參數設計。

This paper studies printing scheduling with a constrained number of colors, which focuses on solving the knapsack packing problem with overlaps among items. Each printing order demands a subset of colors to start its processing. The research question addressed in this paper is to find a solution, a set containing the largest number of printing orders subject to the constraint that the total number of distinct colors involved does not exceed a specified limit. We use an integer programming formulation to describe the problem and to find optimal solutions. Meanwhile, we develop a simulated annealing algorithm to obtain approximate solutions. Through a computational study, we compare the efficiency and quality of these two algorithms. In the optimal solution experiment, we compare the impacts of each parameter in this problem. Also, in the approximate solution experiment, we design parameters of simulated annealing algorithm in this problem.