Skip to main content
SpringerLink
Log in

Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bachman, A., & Janiak, A. (2004). Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society, 55, 257–264.

    Article  Google Scholar 

  • Badiru, A. B. (1992). Computational survey of univariate and multivariate learning curve models. IEEE transactions on Engineering Management, 39, 176–188.

    Article  Google Scholar 

  • Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115, 173–178.

    Article  Google Scholar 

  • Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.

    Article  Google Scholar 

  • Cheng, T. C. E., & Wang, G. (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research, 98, 273–290.

    Article  Google Scholar 

  • Cheng, T. C. E., Wu, C. C., & Lee, W. C. (2008a). Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Information Sciences, 178(11), 2476–2487.

    Article  Google Scholar 

  • Cheng, T. C. E., Wu, C. C., & Lee, W. C. (2008b). Some scheduling problems with deteriorating jobs and learning effects. Computers & Industrial Engineering, 54(4), 972–982.

    Article  Google Scholar 

  • Cheng, T. C. E., Lai, P.-J., Wu, C.-C., & Lee, W.-C. (2009). Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations. Information Sciences, 197, 3127–3135.

    Article  Google Scholar 

  • Eren, T. (2009). A bicriteria parallel machine scheduling with a learning effect of setup and removal times. Applied Mathematical Modelling, 33, 1141–1150.

    Article  Google Scholar 

  • Eren, T., & Guner, E. (2007a). A bicriteria scheduling with a learning effect: total completion time and total tardiness. INFOR: Information Systems and. Operational Research, 45, 75–81.

    Google Scholar 

  • Eren, T., & Guner, E. (2007b). Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling, 31, 1351–1361.

    Article  Google Scholar 

  • Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guided tour to the theory of NP-completeness. San Francisco: Freeman.

    Google Scholar 

  • Gonzalez, T., & Sahni, S. (1978). Flowshop and jobshop schedules: Complexity and approximation. Operations Research, 26, 36–52.

    Article  Google Scholar 

  • Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326.

    Article  Google Scholar 

  • Hoogeveen, J. A., & Kawaguchi, T. (1999). Minimizing total completion time in a two-machine flowshop: Analysis of special cases. Mathematics of Operations Research, 24, 887–910.

    Article  Google Scholar 

  • Jaber, Y. M., & Bonney, M. (1999). The economic manufacture/order quantity (EMQ/EOQ) and the learning curve: past, present, and future. International Journal of Production Economics, 59, 93–102.

    Article  Google Scholar 

  • Janiak, A., & Rudek, R. (2008a). A new approach to the learning effect: beyond the learning curve restrictions. Computers and Operations Research, 35, 3727–3736.

    Article  Google Scholar 

  • Janiak, A., & Rudek, R. (2008b). Experience based approach to scheduling problems with the learning effect. IEEE Transactions on Systems, Man, and Cybernetics-Part A, 39(2), 344–357.

    Article  Google Scholar 

  • Janiak, A., Janiak, W., Rudek, R., & Wielgus, A. (2009). Solution algorithms for the makespan minimization problem with the general learning model. Computers and Industrial Engineering, 56, 1301–1308.

    Article  Google Scholar 

  • Johnson, S. M. (1954). Optimal two-and-three-stage production schedules. Naval Research Logistics, 1, 61–68.

    Article  Google Scholar 

  • Koulamas, C., & Kyparisis, G. J. (2005). Algorithms with performance guarantees for flow shops with regular objective functions. IIE Transactions, 37, 1107–1111.

    Article  Google Scholar 

  • Koulamas, C., & Kyparisis, G. J. (2007). Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 178, 402–407.

    Article  Google Scholar 

  • Lee, W.-C., & Wu, C.-C. (2004). Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics, 88, 85–93.

    Article  Google Scholar 

  • Lee, W.-C., & Wu, C.-C. (2009). Some single-machine and m-machine flowshop scheduling problems with learning considerations. Information Sciences, 179, 3885–3892.

    Article  Google Scholar 

  • Lee, W.-C., Wu, C.-C., & Sung, H.-J. (2004). A bi-criterion single-machine scheduling problem with learning considerations. Acta Informatica, 40, 303–315.

    Article  Google Scholar 

  • Mosheiov, G. (2001a). Scheduling problems with a learning effect. European Journal of Operational Research, 132, 687–693.

    Article  Google Scholar 

  • Mosheiov, G. (2001b). Parallel machine scheduling with a learning effect. Journal of the Operational Research Society, 52, 1165–1169.

    Article  Google Scholar 

  • Mosheiov, G. (2008). Minimizing total absolute deviation of job completion times: Extensions to position-dependent processing times and parallel identical machines. Journal of the Operational Research Society, 59, 1422–1424.

    Article  Google Scholar 

  • Mosheiov, G., & Sarig, A. (2008). A due-window assignment problem with position-dependent processing times. Journal of the Operational Research Society, 59, 997–1003.

    Article  Google Scholar 

  • Mosheiov, G., & Sidney, J. B. (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147, 665–670.

    Article  Google Scholar 

  • Mosheiov, G., & Sidney, J. B. (2005). Note on scheduling with general learning curves to minimize the number of tardy jobs. Journal of the Operational Research Society, 56, 110–112.

    Article  Google Scholar 

  • Pinedo, M. (2002). Scheduling: theory, algorithms and systems. Englewood Cliffs: Prentice Hall.

    Google Scholar 

  • Rothkopf, M. H. (1966). Scheduling independent tasks on parallel processors. Management Science, 12, 437–447.

    Article  Google Scholar 

  • Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3, 59–66.

    Article  Google Scholar 

  • Smutnicki, C. (1998). Some results of worst-case analysis for flow shop scheduling. European Journal of Operational Research, 109, 66–87.

    Article  Google Scholar 

  • Townsend, W. (1978). The single machine problem with quadratic penalty function of completion times: a branch-and-bound solution. Management Science, 24, 530–534.

    Article  Google Scholar 

  • Wang, J.-B. (2005). Flow shop scheduling jobs with position-dependent processing times. Journal of Applied Mathematics and Computing, 18, 383–391.

    Article  Google Scholar 

  • Wang, J.-B., & Xia, Z.-Q. (2005). Flow shop scheduling with a learning effect. Journal of the Operational Research Society, 56, 1325–1330.

    Article  Google Scholar 

  • Wang, J.-B., & Wang, J.-J. (2011a). Single-machine scheduling jobs with exponential learning functions. Computers & Industrial Engineering, 60, 755–759.

    Article  Google Scholar 

  • Wang, J.-B., & Wang, M.-Z. (2011b). A revision of machine scheduling problems with a general learning effect. Mathematical and Computer Modelling, 53, 330–336.

    Article  Google Scholar 

  • Wang, J.-B., Ng, C. T., Cheng, T. C. E., & Liu, L. L. (2008). Single-machine scheduling with a time-dependent learning effect. International Journal of Production Economics, 111, 802–811.

    Article  Google Scholar 

  • Wang, J.-B., Sun, L.-H., & Sun, L.-Y. (2010). Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect. Applied Mathematical Modelling, 34, 2813–2819.

    Article  Google Scholar 

  • Wright, T. P. (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 3, 122–128.

    Google Scholar 

  • Wu, C.-C., & Lee, W.-C. (2008). Single-machine scheduling problems with a learning effect. Applied Mathematical Modelling, 32(7), 1191–1197.

    Article  Google Scholar 

  • Wu, C.-C., & Liu, C.-L. (2010). Minimizing the makespan on a single machine with learning and unequal release times. Computers & Industrial Engineering, 59, 419–424.

    Article  Google Scholar 

  • Wu, C.-C., Hsu, P.-H., Chen, J.-C., & Wang, N.-S. (2011). Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. Computers & Operations Research, 38, 1025–1034.

    Article  Google Scholar 

  • Xu, Z., Sun, L., & Gong, J. (2008). Worst-case analysis for flow shop scheduling with a learning effect. International Journal of Production Economics, 113, 748–753.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Science, Shenyang Aerospace University, Shenyang, 110136, China

    Ji-Bo Wang

  2. School of Management Science and Engineering, Dalian University of Technology, Dalian, 116024, China

    Ming-Zheng Wang

Authors
  1. Ji-Bo Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ming-Zheng Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ji-Bo Wang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, JB., Wang, MZ. Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects. Ann Oper Res 191, 155–169 (2011). https://doi.org/10.1007/s10479-011-0923-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-011-0923-2

Keywords

Search

Navigation