標題: A simple lower bound for total completion time minimization in a two-machine flowshop
作者: Lin, BMT
Wu, JM
資訊管理與財務金融系 註:原資管所+財金所
Department of Information Management and Finance
關鍵字: flowshop;total completion time;lower bound;branch-and-bound algorithm
公開日期: 1-Sep-2005
摘要: The purpose of this study is to present a simple lower bound to facilitate the development of branch-and-bound algorithms for the minimization of total completion time in a two-machine flowshop. The studied problem is known to be strongly NP-hard. In the literature, several lower bounds have been proposed. The bounding technique addressed in this paper is based upon a concept about rearrangement of the parameters of the input instance. The technique is intrinsically simple for computer implementations. We conduct computational experiments for problems with 10-65 jobs. Numerical results from our computational study indicate that the new scheme is very effective in reducing the execution time needed for composing optimal solutions.
URI: http://dx.doi.org/10.1142/S0217595905000601
http://hdl.handle.net/11536/13330
ISSN: 0217-5959
DOI: 10.1142/S0217595905000601
期刊: ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH
Volume: 22
Issue: 3
起始頁: 391
結束頁: 407
Appears in Collections:Articles