A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP

B. M. T. Lin () and J. M. Wu
Additional contact information
B. M. T. Lin: Department of Information and Finance Management, Institute of Information Management, National Chiao Tung University, Hsinchu, Taiwan 300, R.O.C.
J. M. Wu: Department of Information Management, National Chi Nan University, Puli, Taiwan 545, R.O.C.

Asia-Pacific Journal of Operational Research (APJOR), 2005, vol. 22, issue 03, 391-407

Abstract: 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.

Keywords: Flowshop; total completion time; lower bound; branch-and-bound algorithm (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595905000601
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:22:y:2005:i:03:n:s0217595905000601

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595905000601

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().