查詢結果分析
來源資料
頁籤選單縮合
題 名 | Solving Generalized Assignment Problem Using Lagrangian Relaxation Approach=以拉氏鬆弛法求解一般化指派問題 |
---|---|
作 者 | 吳泰熙; 葉進儀; 張欽智; | 書刊名 | 品質學報 |
卷 期 | 12:4 民94.12 |
頁 次 | 頁313-322 |
分類號 | 494.542 |
關鍵詞 | 製造單元形成問題; 一般化指派問題; 拉氏鬆弛演算法; Generalized assignment problem; Lagrangian relaxation; |
語 文 | 英文(English) |
中文摘要 | 一般化指派問題尋求最大利潤或最小成本之工作指派計畫,其應用面非常廣泛,常見之製造單元形成問題即是一例。本文提出一以拉氏鬆弛法LR來求解一般化指派問題,演算法LR透過發展一快速搜尋起始可行解,再結合適當之演算參數設定,結合成一有效求解之拉氏鬆弛演算法。為驗證本演算法之效用及效率,我們採用了84題文獻範例,並與現存文獻標竿演算結果做一比較後,發現LR可以於極短之演算時間內求得品質甚佳之演算結果,部分結果甚至超越文獻結果,成為迄今最佳之演算結果。 |
英文摘要 | The generalized assignment problem (GAP) determines the maximum profit or minimum cost assignment of n jobs to m agents. In this paper, a Lagrangian relaxation heuristic, LR is presented to solve the GAPs. 84 standard set of test problems adopted from the literature are used to evaluate the performance of the proposed algorithm, and compare with other existing methods. Some solutions generated by the proposed LR algorithm even surpass existing benchmark methods in both small and large-sized problems. The LR can find solutions with good quality very efficiently, and should thus be useful to practitioners and researchers. |
本系統中英文摘要資訊取自各篇刊載內容。