Abstract
This article considers flow shop scheduling problems with a learning effect. By the learning effect, we mean that the processing time of a job is defined by a function of its position in a processing permutation. The objective is to minimize the total weighted completion time. Some heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems are presented, and the worst-case bound of these heuristics are also analyzed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Badiru, A. B. (1992). Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management, 39, 176–188.
Biskup, D. (2008). A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research, 188, 315–329.
Brucker, P., Knust, S., Cheng, T. C. E., & Shakhlevich, N. V. (2004). Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Annals of Operations Research, 129, 81–106.
Cheng, T. C. E., & Janiak, A. (2000). A permutation flow-shop scheduling problem with convex models of operation processing times. Annals of Operations Research, 96, 39–60.
Gonzalez, T., & Sahni, S. (1978). Flowshop and jobshop schedules: complexity and approximation. Operations Research, 26, 36–52.
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.
Gupta, J. N. D., Koulamas, C. P., Kyparisis, G. J., Potts, C. N., & Strusevich, V. A. (2004). Scheduling three-operation jobs in a two-machine flow shop to minimize makespan. Annals of Operations Research, 129, 171–185.
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.
Johnson, S. M. (1954). Optimal two-and-three-stage production schedules. Naval Research Logistics, 1, 61–68.
Koulamas, C., & Kyparisis, G. J. (2005). Algorithms with performance guarantees for flow shops with regular objective functions. IIE Transactions, 37, 1107–1111.
Lee, W.-C., & Chung, Y.-H. (2013). Permutation flowshop scheduling to minimize the total tardiness with learning effects. International Journal of Production Economics, 141, 327–334.
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 Economics, 142, 98–104.
Rudek, R. (2011). Computational complexity and solution algorithms for flowshop scheduling problems with learning effect. Computers & Industrial Engineering, 61, 20–31.
Shchepin, E. V., & Vakhania, N. (2008). On the geometry, preemptions and complexity of multiprocessor and shop scheduling. Annals of Operations Research, 159, 183–213.
Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics, 3, 59–66.
Smutnicki, C. (1998). Some results of worst-case analysis for flow shop scheduling. European Journal of Operational Research, 109, 66–87.
Tanrisever, F., & Kutanoglu, E. (2008). Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: single machine problem. Annals of Operations Research, 159, 5–24.
Wang, J.-B., & Wang, M.-Z. (2011). Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects. Annals of Operations Research, 191, 155–169.
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 Society, 63, 130–137.
Wang, J.-B., & Xia, Z.-Q. (2005). Flow shop scheduling with a learning effect. Journal of the Operational Research Society, 56, 1325–1330.
Wang, J.-B., Ji, P., Cheng, T. C. E., & Wang, D. (2012a). Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optimization Letters, 6, 1393–1409.
Wang, J.-B., Wu, Y.-B., & Ji, P. (2012b). A revision of some single-machine and m-machine flowshop scheduling problems with learning considerations. Information Sciences, 190, 227–232.
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.
Xu, K., Feng, Z., & Ke, L. (2011). Single machine scheduling with total tardiness criterion and convex controllable processing times. Annals of Operations Research, 186, 383–391.
Yau, H., & Shi, L. (2009). Nested partitions for the large-scale extended job shop scheduling problem. Annals of Operations Research, 168, 23–39.
Zhang, X., Yan, G., Huang, W., & Tang, G. (2011). Single-machine scheduling problems with time and position dependent processing times. Annals of Operations Research, 186, 345–356.
Zhao, C., Zhang, Q., & Tang, H. (2002). A flowshop scheduling algorithm to minimize total weighted completion times. OR Transactions, 6(4), 50–56.
Acknowledgements
We are grateful to two anonymous referees for their helpful comments on an earlier version of this paper. This research was supported by the open project of The State Key Laboratory for Manufacturing Systems Engineering (Grant no. sklms2012009), the Program for Shanxi Natural Science Foundation research (Grant no. 2012JQ9006) and the National Natural Science Foundation of China (Grant No. 71272117).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sun, LH., Cui, K., Chen, JH. et al. Some results of the worst-case analysis for flow shop scheduling with a learning effect. Ann Oper Res 211, 481–490 (2013). https://doi.org/10.1007/s10479-013-1368-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-013-1368-6