Abstract
We consider a two-machine flow shop scheduling problem with effects of deterioration and learning. By the effects of deterioration and learning, we mean that the processing time of a job is a function of its execution starting time and its position in a sequence. The objective is to find a sequence that minimizes the makespan. Several dominance properties and two lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. Two heuristic algorithms are also proposed to obtain near-optimal solutions. Computational results are presented to evaluate the performance of the proposed algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alidaee B., Womer N.K.: Scheduling with time dependent processing processing times: review and extensions. J. Oper. Res. Soc. 50, 711–720 (1999)
Biskup D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115, 173–178 (1999)
Biskup D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188, 315–329 (2008)
Cheng T.C.E., Ding Q., Lin BMT.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152, 1–13 (2004)
Cheng T.C.E., Wu C.-C., Lee W.C.: Some scheduling problems with sum-of-processing -times-based and job-position-based learning effects. Inf. Sci. 178, 2476–2487 (2008)
Cheng T.C.E., Wu C.-C., Lee W.C.: Some scheduling problems with deteriorating jobs and learning effects. Comput. Ind. Eng. 54, 972–982 (2008)
Floudas, C.A., Pardalos, P.M.: Encyclopedia of Optimization. 2nd ed. Springer (2009)
Gawiejnowicz, S.: Time-dependent scheduling. Springer (2008)
Hadda H.: A (\({\frac{4}{3}}\))-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints. Optim. Lett. 3, 583–592 (2009)
Lee W.-C.: A note on deteriorating jobs and learning in single-machine scheduling problems. Int. J. Bus. Econ. 3, 83–89 (2004)
Lee W.-C., Wu C.-C.: Minimizing total completion time in a two-machine flowshop with a learning effect. Int. J. Prod. Econ. 88, 85–93 (2004)
Lee W-C., Wu C-C.: A two-machine flowshop makespan scheduling problem with deteriorating jobs. Comput. Ind. Eng. 54, 737–749 (2008)
Lee W-C., Wu C-C., Hsu P-H.: A single-machine learning effect scheduling problem with release times. Omega Int. J. Manag. Sci. 38, 3–11 (2010)
Lee C.-Y., Yu G.: Parallel-machine scheduling under potential disruption. Optim. Lett. 2, 27–37 (2008)
Mosheiov G.: Complexity analysis of job-shop scheduling with deteriorating jobs. Discret. Appl. Math. 117, 195–209 (2002)
Nembhard DA., Osothsilp N.: Task complexity effects on between-individual learning/forgetting variability. Int. J. Ind. Ergonomics 29, 297–306 (2002)
Ng C.T., Wang J.-B., Cheng T.C.E., Liu L.-L.: A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs. Comput. Oper. Res. 37, 83–90 (2010)
Pardalos P.M., Resende M.G.C.: Handbook of Applied Optimization. Oxford Univ Press, USA (2002)
Pardalos P.M.: Complexity in Numerical Optimization. World Scientific, USA (1993)
Setamaa-Karkkainen A., Miettinen K., Vuori J.: Heuristic for a new multiobjective scheduling problem. Optim. Lett. 1, 213–225 (2007)
Shiau Y.-R., Lee W.-C., Wu C.-C., Chang C.-M.: Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration. Int. J. Adv. Manuf. Technol. 34, 774–782 (2007)
Toksar M.D., Guner E.: Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach. Int. J. Adv. Manuf. Technol. 38, 801–808 (2008)
Wang C., Chu C., Proth J.M.: Efficient heuristic and optimal approaches for \({n/2/F/\sum C_i}\) scheduling problems. Int. J. Prod. Econ. 44, 225–237 (1996)
Wang J.-B., Liu L.-L.: Two-machine flow shop problem with effects of deterioration and learning. Comput. Ind. Eng. 57, 1114–1121 (2009)
Wang, J.-B., Wang, M.-Z.: Single-machine scheduling with nonlinear deterioration. Optim. Lett. doi:10.1007/s11590-010-0253-3
Wang, X.-Y., Wang, D., Yin, N.: A note on single-machine scheduling with nonlinear deterioration. Optim. Lett. doi:10.1007/s11590-011-0295-1
Wu C.-C., Lee W.C.: Single-machine scheduling problems with a learning effect. Appl. Math. Model. 32, 1191–1197 (2008)
Wu C.C., Lee W.C.: Single-machine group scheduling problems with deteriorating setup times and job processing times. Int. J. Prod. Econ. 115, 128–133 (2008)
Wu C.-C., Lee W.-C., Shiau Y.-R.: Minimizing the total weighted completion time on a single machine under linear deterioration. Int. J. Adv. Manuf. Technol. 33, 1237–1243 (2007)
Zhao C.-L., Tang H.-Y.: A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints.. Optim. Lett. 5, 183–190 (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, JB., Ji, P., Cheng, T.C.E. et al. Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optim Lett 6, 1393–1409 (2012). https://doi.org/10.1007/s11590-011-0334-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0334-y