考慮可合併訂單且具有機台容量限制下之出菜排程

Dishing up Scheduling Problem with Capacity Constraint

鍾國言(KUO-YEN CHUNG)

指導教授 ： 曾兆堂

朝陽科技大學/理工學院/工業工程與管理系/碩士(2017年)

摘要

隨著外食人口數增加，除了滿足顧客需求之外，對於顧客等待時間也相當重視。學者林佳羲(2014)在餐廳議題中，提出餐廳生產系統結合排程理論可以有效改善顧客等待時間，維持服務的穩定性。
本研究延伸學者林佳羲(2014)之問題，為了考量到實際餐廳生產流程，加入餐廳兩個特性:合併訂單與機台容量限制，發展出排程問題模型。第一個特性，合併訂單為每張訂單中有相同的菜品，在整理每張訂單時將相同的菜品進行合併處理；第二個特性，機台容量限制為在製餐的過程中，每台烹飪設備都有一定的容量限制。
最後，本研究將提出的變動鄰域結合禁忌搜尋法(Variable Neighborhood with Tabu Search Algorithm)與EDD啟發法做比較。實驗結果顯示，EDD啟發法在小菜品數的情況下效果不彰，針對大菜品數的情況下可獲得不錯的近似解，另外變動鄰域結合禁忌搜尋法在任何菜品數下均可獲得良好的績效。

關鍵字

多訂單工作排程 ； 禁忌搜尋法 ； 變動鄰域搜尋法 ； 群組生產

並列摘要

With the increase in the number of outside eater population, in addition to meet customer needs, the customer waiting time is also very important. Scholar Chia-His Lin (2014) in the restaurant issue, the proposed restaurant production system combined with scheduling theory can effectively improve customer waiting time, and maintain service stability.

In order to consider the actual production process of the restaurant, we added two characteristics of the restaurant: the combined orders and the capacity constraint, and developed the scheduling problem model. 1. The combined orders for the same menu in each order, in the order of each order will be the same dishes for processing; 2. The capacity constraint for the process of making the meal, each cooking equipment has a capacity constraint.

Finally, this research will compare the proposed Variable Neighborhood with Tabu Search algorithm and EDD heuristic algorithm. The experimental results show that the proposed EDD heuristic algorithm will give a not so good performance for the small-sized problems, and a good approximate solution for the large-sized problems. In addition, Variable Neighborhood with Tabu Search algorithm can obtain a good performance for solving this scheduling problem.

並列關鍵字

Multiple orders per job ； Tabu search ； Variable neighborhood search ； Group scheduling

參考文獻

1.潘冠銘，「以瀰集演算法求解流線型製造單元排程」，碩士論文，國立交通大學工業工程與管理學系，新竹(2011)。

2.林耿漢，「以塔布搜尋法求解流線型製造單元排程」，碩士論文，國立交通大學工業工程與管理學系，新竹(2011)。

3.曾偉杰，「以模擬退火法求解流線型製造單元排程」，碩士論文，國立交通大學工業工程與管理學系，新竹(2011)。

4.林奕勳，「以蟻群最佳化演算法求解流線型製造單元排程」，碩士論文，國立交通大學工業工程與管理學系，新竹(2011)。

5.陳威宇，「以粒子群演算法求解流線型製造單元排程」，碩士論文，國立交通大學工業工程與管理學系，新竹(2011)。