×

Research on \(m\)-machine flow shop scheduling with truncated learning effects. (English) Zbl 07766344

Summary: The permutation flow shop problems with truncated exponential sum of logarithm processing times based and position-based learning effects are considered in this study. The objective is to minimize makespan and total weighted completion time, respectively. Several heuristics and a branch-and-bound algorithm are proposed in this paper. The tight worst-case bounds of some simple heuristics are also given. Numerical experiments are tested to evaluate the performance of the heuristics and branch-and-bound algorithm.
{© 2016 The Authors. International Transactions in Operational Research © 2016 International Federation of Operational Research Societies}

MSC:

90-XX Operations research, mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biskup, D., 2008. A state‐of‐the‐art review on scheduling with learning effects. European Journal of Operational Research188, 315-329. · Zbl 1129.90022
[2] Cheng, M., Tadikamalla, P.R., Shang, J., Zhang, B., 2015. Single machine scheduling problems with exponentially time‐dependent learning effects. Journal of Manufacturing Systems34, 60-65.
[3] Cheng, T.C.E., Wu, C.‐C., Chen, J.‐C., Wu, W.‐H., Cheng, S.‐R., 2013. Two‐machine flowshop scheduling with a truncated learning function to minimize the makespan. International Journal of Production Economics141, 79-86.
[4] Defersha, F.M., 2015. A simulated annealing with multiple‐search paths and parallel computation for a comprehensive flowshop scheduling problem. International Transactions in Operational Research22, 669-691. · Zbl 1332.90108
[5] Dhouib, E., Teghem, J., Loukil, T., 2013. Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research20, 213-232. · Zbl 1263.90033
[6] Emmons, H., Vairaktarakis, G., 2013. Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications. Springer, New York.
[7] Framinan, J.M., Leisten, R., 2003. An efficient constructive heuristic for flowtime minimization in permutation flow shops. OMEGA: The International Journal of Management Science31, 311-317.
[8] Gonzalez, T., Sahni, S., 1978. Flowshop and jobshop schedules: complexity and approximation. Operations Research26, 36-52. · Zbl 0371.90061
[9] Juan, A.A., Lourenco, H.R., Mateo, M., Luo, R., Castella, Q., 2014. Using iterated local search for solving the flow‐shop problem: parallelization, parametrization, and randomization issues. International Transactions in Operational Research21, 103-126. · Zbl 1291.90095
[10] Kuo, W.‐H., Hsu, C.‐J., Yang, D.‐L., 2012. Worst‐case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time‐dependent learning effect. Information Sciences184, 282-297. · Zbl 1239.90050
[11] Lee, W.‐C., Chung, Y.‐H., 2013. Permutation flowshop scheduling to minimize the total tardiness with learning effects. International Journal of Production Economics141, 327-334.
[12] Li, J.‐Q., Pan, Q.‐K., 2015. Solving the large‐scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm. Information Sciences316, 487-502.
[13] Li, G., Wang, X.‐Y., Wang, J.‐B., Sun, L.‐Y., 2013. Worst case analysis of flow shop scheduling problems with a time‐dependent learning effect. International Journal of Production Economics142, 98-104.
[14] Liu, Y., Feng, Z., 2014. Two‐machine no‐wait flowshop scheduling with learning effect and convex resource‐dependent processing times. Computers & Industrial Engineering75, 170-175.
[15] Lu, Y.‐Y., Teng, F., Feng, Z.‐X., 2015. Scheduling jobs with truncated exponential sum‐of‐logarithm‐processing‐times based and position‐based learning effects. Asia‐Pacific Journal of Operational Research32, 3, 1550026. · Zbl 1325.90047
[16] Nawaz, M., Enscore, Jr. E.E., Ham, I., 1983. A heuristic algorithm for the m‐machine, n‐job flow‐shop sequencing problem. OMEGA: The International Journal of Management Science11, 91-95.
[17] Nowicki, E., Smutnicki, C., 1996. A fast tabu search algorithm for the permutation flow‐shop problem. European Journal of Operational Research91, 160-175. · Zbl 0947.90590
[18] Nowicki, E., Smutnicki, C., 1998. The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research106, 226-253. · Zbl 0991.90059
[19] Pan, Q.‐K., Ruiz, R., 2013. A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers and Operations Research40, 1, 117-128. · Zbl 1349.90386
[20] Pinedo, M., 2002. Scheduling: Theory, Algorithms and Systems. Prentice Hall, Englewood Cliffs, NJ. · Zbl 1145.90394
[21] Rudek, R., 2011. Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Computers & Industrial Engineering61, 20-31.
[22] Sun, L.‐H., Cui, K., Chen, J.‐H., Wang, J., He, X.‐C., 2013a. Research on permutation flow shop scheduling problems with general position‐dependent learning effects. Annals of Operations Research211, 473-480. · Zbl 1286.90066
[23] Sun, L.‐H., Cui, K., Chen, J.‐H., Wang, J., He, X.‐C., 2013b. Some results of the worst‐case analysis for flow shop scheduling with a learning effect. Annals of Operations Research211, 481-490. · Zbl 1286.90067
[24] Taillard, E., 1990. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research47, 65-74. · Zbl 0702.90043
[25] Wang, J.‐B., Wang, J.‐J., 2014. Flowshop scheduling with a general exponential learning effect. Computers & Operations Research43, 292-308. · Zbl 1348.90321
[26] Wang, J.‐B., Wang, M.‐Z., 2012. Worst‐case analysis for flow shop scheduling problems with an exponential learning effect. Journal of the Operational Research Society63, 130-137.
[27] Wang, J.‐J., Zhang, B.‐H., 2015. Permutation flowshop problems with bi‐criterion makespan and total completion time objective and position‐weighted learning effects. Computers & Operations Research58, 24-31. · Zbl 1348.90322
[28] Wang, X.‐Y., Zhou, Z., Zhang, X., Ji, P., Wang, J.‐B., 2013. Several flow shop scheduling problems with truncated position‐based learning effect. Computers & Operations Research40, 2906-2929. · Zbl 1348.90323
[29] Wu, C.‐C., Lee, W.‐C., 2009. A note on the total completion time problem in a permutation flowshop with a learning effect. European Journal of Operational Research192, 343-347. · Zbl 1180.90144
[30] Xie, Z., Zhang, C., Shao, X., Lin, W., Zhu, H., 2014. An effective hybrid teaching-learning‐based optimization algorithm for permutation flow shop scheduling problem. Advances in Engineering Software77, 35-47.
[31] Xu, Z., Sun, L., Gong, J., 2008. Worst‐case analysis for flow shop scheduling with a learning effect. International Journal of Production Economics113, 748-753.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.