A note on the total completion time problem in a permutation flowshop with a learning effect. (English) Zbl 1180.90144

Summary: The concept of learning process plays a key role in production environments. However, it is relatively unexplored in the flowshop setting.
In this short note, we consider a permutation flowshop scheduling problem with a learning effect where the objective is to minimize the sum of completion times or flowtime. A dominance rule and several lower bounds are established to speed up the search for the optimal solution. In addition, the performances of several well-known heuristics are evaluated when the learning effect is present.


90B35 Deterministic scheduling theory in operations research


Full Text: DOI


[1] Bansal, S.P., Minimizing the sum of completion times of n jobs over m machines in a flowshop – a branch and bound approach, AIIE transactions, 9, 306-311, (1977)
[2] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[3] Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, (2007)
[4] Chung, C.S.; Flynn, J.; Kirca, O., A branch-and-bound algorithm to minimize the total flow time for m-machine permutation flowshop problems, International journal of production economics, 79, 185-196, (2002)
[5] Framinan, J.M.; Leisten, R., An efficient constructive heuristic for flowtime minimization in permutation flow shops, OMEGA: the international journal of management science, 31, 311-317, (2003)
[6] Framinan, J.M., Leisten R., Gupta, J.N.D., 2001. A review and classification heuristics for permutation flow shop scheduling with makespan objective. Technical Report, Industrial Management. University of Seville. · Zbl 1088.90022
[7] Framinan, J.M.; Leisten, R.; Ruiz-Usano, R., Comparison of heuristics for flowtime minimization in permutation flowshops, Computers and operations research, 32, 1237-1254, (2005) · Zbl 1074.90017
[8] Lenstra, J.K.; Rinnooy Kan, A.H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of discrete mathematics, 1, 343-362, (1977) · Zbl 0301.90025
[9] Liu, J.Y.; Reeves, C.R., Constructive and composite heuristic solutions to the \(P / / \sum C_i\) scheduling problem, European journal of operational research, 132, 439-452, (2001) · Zbl 1134.90389
[10] Mosheiov, G., Scheduling problems with a learning effect, European journal of operational research, 132, 687-693, (2001) · Zbl 1017.90051
[11] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, European journal of operational research, 147, 665-670, (2003) · Zbl 1037.90529
[12] Nawaz, M.; Enscore, E.E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA: the international journal of management science, 11, 91-95, (1983)
[13] Rajendran, C.; Ziegler, H., An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, European journal of operational research, 103, 129-138, (1997) · Zbl 0922.90089
[14] Wang, J.B.; Xia, Z.Q., Flow-shop scheduling with a learning effect, Journal of the operational research society, 56, 1325-1330, (2005) · Zbl 1082.90041
[15] Woo, D.S.; Yim, H.S., A heuristic algorithm for Mean flowtime objective in scheduling, Computers and operations research, 25, 175-182, (1998) · Zbl 0904.90090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.