×
Wu, Chin-Chia; Hsu, Peng-Hsiang; Chen, Juei-Chao; Wang, Nae-Sheng

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. (English) Zbl 1205.90139

Comput. Oper. Res. 38, No. 7, 1025-1034 (2011).
Summary: This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.

Cited in 16 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

genetic heuristic algorithm; scheduling; sum-of-processing time based learning effect; release time
PDF BibTeX XML Cite
\textit{C.-C. Wu} et al., Comput. Oper. Res. 38, No. 7, 1025--1034 (2011; Zbl 1205.90139)
Full Text: DOI

References:

[1] Heiser, J.; Render, B., Operations Management (1999), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[2] Russell, R.; Taylor, B. W., Operations Management: multimedia version (2000), Prentice Hall: Prentice Hall Upper Saddle River, NJ
[3] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[4] Cheng, T. C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of Operations Research, 98, 273-290 (2000) · Zbl 0967.68019
[5] Janiak, A.; Rudek, R., The learning effect: getting to the core of the problem, Information Processing Letters, 103, 183-187 (2007) · Zbl 1184.68405
[6] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, Journal of the Operational Research Society, 55, 257-264 (2004) · Zbl 1095.90033
[7] Wang, J. B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 4, 397-402 (2007)
[8] 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, Information Sciences, 178, 2476-2487 (2008) · Zbl 1172.90397
[9] Wang, J. B.; Ng, C. T.; Cheng, T. C.E.; Liu, L. L., Single-machine scheduling with a time-dependent learning effect, International Journal of Production Economics, 111, 802-811 (2008)
[10] Janiak, A.; Rudek, R., A new approach to the learning effect: beyond the learning curve restrictions, Computers and Operations Research, 35, 3727-3736 (2008) · Zbl 1170.90392
[11] Wang, J. B.; Wang, D.; Wang, L. Y.; Lin, L.; Yin, N.; Wang, W. W., Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times, Computers and Mathematics with Applications, 57, 9-16 (2009) · Zbl 1165.90471
[12] Wang, J. B., Single-machine scheduling with general learning functions, Computers and Mathematics with Applications, 56, 1941-1947 (2008) · Zbl 1165.90470
[13] Wang, J. B., Single machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Computers & Industrial Engineering, 55, 3, 584-591 (2008)
[14] Sun, L., Single-machine scheduling problems with deteriorating jobs and learning effects, Computers & Industrial Engineering, 57, 843-846 (2009)
[15] Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179, 2416-2425 (2009) · Zbl 1166.90342
[16] Wu, C. C.; Lee, W. C., Single-machine and flowshop scheduling with a general learning effect model, Computers & Industrial Engineering, 56, 4, 1553-1558 (2009)
[17] Toksari, M. D.; Oron, D.; Güner, E., Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning, Mathematical and Computer Modelling, 50, 401-406 (2009) · Zbl 1185.90097
[18] Zhang, X.; Yan, G., Machine scheduling problems with a general learning effect, Mathematical and Computer Modelling, 51, 84-90 (2010) · Zbl 1190.90076
[19] Huang, X.; Wang, J. B.; Wang, L. Y.; Gao, W. J.; Wang, X. R., Single machine scheduling with time-dependent deterioration and exponential learning effect, Computers & Industrial Engineering, 58, 58-63 (2010)
[20] Wang, J. B., Single machine scheduling with a time-dependent learning effect and deteriorating jobs, Journal of the Operational Research Society, 60, 583-586 (2009) · Zbl 1163.90515
[21] Toksari, M. D.; Isleyen, S. K.; Güner, E.; Baykoç, Ö. F., Assembly line balancing problem with deterioration tasks and learning effect, Expert Systems with Applications, 37, 1223-1228 (2010)
[22] Wang, J. B.; Liu, L. L., Two-machine flow shop problem with effects of deterioration and learning, Computers & Industrial Engineering, 57, 1114-1121 (2009)
[23] Biskup, D., A state-of-the-art review on scheduling with learning effect, European Journal of Operational Research, 188, 315-329 (2008) · Zbl 1129.90022
[24] Wang, J. B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 34, 309-313 (2010) · Zbl 1185.90099
[25] Janiak, A.; Janiak, W. A.; Rudek, R.; Wielgus, A., Solution algorithms for the makespan minimization problem with the general learning model, Computers & Industrial Engineering, 56, 1301-1308 (2009)
[26] Wang, J. B., Single-machine scheduling with a sum-of-actual-processing-time-based learning effect, Journal of the Operational Research Society, 61, 172-177 (2010) · Zbl 1193.90115
[27] Wang, J. B.; Sun, L.; Sun, L., Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect, Applied Mathematical Modelling, 34, 2813-2819 (2010) · Zbl 1201.90088
[28] Janiak, A.; Rudek, R., Experience-based approach to scheduling problems with the learning effect, IEEE Transactions on Systems, Man, and Cybernetics—Part A, 39, 344-357 (2009)
[29] Janiak, A.; Rudek, R., A note on a makespan minimization problem with a multi-ability learning effect, Omega, 38, 213-217 (2010)
[30] Lee, W. C.; Wu, C. C.; Hsu, P. H., A single-machine learning effect scheduling problem with release times, Omega: The International Journal of Management Science, 38, 3-11 (2010)
[31] Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect, Applied Mathematics and Computation, 208, 355-358 (2009) · Zbl 1155.90380
[32] Lee, W. C.; Wu, C. C.; Liu, M. F., A single-machine bi-criterion learning scheduling problem with release times, Expert Systems with Applications, 36, 10295-10303 (2009)
[33] 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
[34] Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1967), Cambridge University Press: Cambridge University Press London · Zbl 0634.26008
[35] Beasley, D.; Bull, D.; Martin, R. R., An overview of genetic algorithms, part 1: fundamentals, Journal of University Computing, 15, 58-69 (1993)
[36] Iyer, S. K.; Saxena, B. S., Improved genetic algorithm for the permutation flowshop scheduling problem, Computers and Operations Research, 31, 593-606 (2004) · Zbl 1046.90028
[37] Chen, J. S.; Pan, J. C.H.; Lin, C. M., A hybrid genetic algorithm for the reentrant flow-shop scheduling problem, Expert Systems with Applications, 34, 570-577 (2008)
[38] Chou, F. D., An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem, Expert Systems with Applications, 36, 3857-3865 (2009)
[39] Ugur, A., Path planning on a cuboid using genetic algorithms, Information Sciences, 178, 16, 3275-3287 (2008) · Zbl 1154.68512
[40] Darwin, C. R., On the Origin of Species through Natural Selection (1859), John Murray: John Murray London
[41] Holland, J., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor
[42] Essafi, I.; Matib, Y.; Dauzere-Peres, S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers and Operations Research, 35, 2599-2616 (2008) · Zbl 1177.90155
[43] Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A generic algorithm for flow shop scheduling problems, Journal of Operations Research Society, 55, 8, 830-835 (2004) · Zbl 1060.90035
[44] Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal of Computing, 6, 154-160 (1994) · Zbl 0807.90060
[45] Reeves, C., Heuristics for scheduling a single machine subject to unequal job release times, European Journal of Operational Research, 80, 397-403 (1995)
[46] Chen, C. L.; Vempati, V. S.; Aljaber, N., An application of genetic algorithms for flow shop problems, European Journal of Operations Research, 80, 389-396 (1995)
[48] Etiler, O.; Toklu, B., Comparison of genetic crossover operators using in scheduling problems, Journal of the Institute of Technology, Gazi University, Turkey, 14, 21-32 (2001)
[49] Chu, C. B., A branch-and-bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics, 39, 859-875 (1992) · Zbl 0766.90039
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.