Abstract
This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Biskup D (1999). Single-machine scheduling with learning considerations. Eur J Opl Res 115: 173–178.
Cheh KM, Goldberg JB and Askin RG (1991). A note on the effect of neighborhood structure in simulated annealing. Comput Oper Res 18: 537–547.
Dileepan P and Sen T (1988). Bicriterion static scheduling research for a single machine. Omega 16: 53–59.
Fisher ML (1971). A dual algorithm for the one-machine scheduling problem. Math Program 11: 229–251.
Garey MR, Johnson DS and Sethi PR (1979). The complexity of flowshop and jobshop scheduling. Math Opl Res 1: 117–129.
Heiser J and Render B (1999). Operations Management, 5th edn. Prentice Hall: Englewood Cliffs, NJ.
Karasakal EK and Köksalan M (2000). A simulated annealing approach to bicriteria scheduling problems on a single machine. J Heurist 6: 311–327.
Kirkpatrick S, Gellat CD and Vecchi MP (1983). Optimization by simulated annealing algorithm. Science 220: 671–680.
Koulamas C, Antony SR and Jaen R (1994). A survey of simulated annealing applications to operations research problems. Omega 22: 41–56.
Lee WC and Wu CC (2004). Minimizing total completion time in a two-machine flowshop with a learning effect. Int J Prod Econom 88: 85–93.
Lee WC, Wu CC and Sung HJ (2004). A bi-criterion single-machine scheduling problem with learning considerations. Acta Informatica 40: 303–315.
Lenstra JK, Rinnooy AHG and Brucker P (1977). Complexity of machine scheduling problems. Ann Discr Math 1: 1016–1019.
Mosheiov G (2001a). Scheduling problems with a learning effect. Eur J Opl Res 132: 687–693.
Mosheiov G (2001b). Parallel machine scheduling with a learning effect. J Opl Res Soc 52: 1165–1169.
Mosheiov G and Sidney J (2003). Scheduling with general job-dependent learning curves. Eur J Opl Res 147: 665–670.
Nagar A, Haddock J and Heragu S (1995a). Multiple and bicriteria scheduling: a literature survey. Eur J Opl Res 81: 88–104.
Nagar A, Heragu SS and Haddock J (1995b). A branch-and-bound approach for a two-machine flowshop scheduling problem. J Opl Res Soc 46: 721–734.
Panwalker SS and Iskander W (1977). A survey of scheduling rules. Oper Res 25: 45–61.
Ruiz-Torres AJ, Enscore EE and Barton RR (1997). Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem. Comput Ind Eng 33: 257–260.
Russell R and Taylor III BW (2000). Operations Management: Multimedia Version, 3rd edn. Prentice-Hall: Upper Saddle River, NJ.
Wright TP (1936). Factors affecting the cost of airplanes. J Aeronaut Sci 3: 122–128.
Yelle LE (1979). The learning curve: historical review and comprehensive survey. Decis Sci 10: 302–328.
Acknowledgements
The authors are grateful to the editor and the referee, whose constructive comments have led to a substantial improvement in the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, P., Wu, CC. & Lee, WC. A bi-criteria two-machine flowshop scheduling problem with a learning effect. J Oper Res Soc 57, 1113–1125 (2006). https://doi.org/10.1057/palgrave.jors.2602095
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/palgrave.jors.2602095