Solving a two-agent single-machine scheduling problem considering learning effect. (English) Zbl 1251.90165

Summary: Scheduling with multiple agents and learning effect has drawn much attention. We investigate the job scheduling problem of two agents competing for the usage of a common single machine with learning effect. The objective is to minimize the total weighted completion time of both agents with the restriction that the makespan of either agent cannot exceed an upper bound. In order to solve this problem we develop several dominance properties and a lower bound based on a branch-and-bound to find the optimal algorithm, and derive genetic algorithm based procedures for finding near-optimal solutions. The performances of the proposed algorithms are evaluated and compared via computational experiments.


90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Curiel, I.; Pederzoli, G.; Tijs, S., Sequencing games, European journal of operational research, 40, 344-351, (1989) · Zbl 0674.90107
[2] Hamers, H.; Borm, P.; Tijs, S., On games corresponding to sequencing situations with ready times, Mathematical programming, 69, 471-483, (1995) · Zbl 0844.90120
[3] Schultz D, Oh SH, Grecas CF, Albani M, Sanchez J, Arbib C, Arvia V, Servilio M, Sorbo FD, Giralda A, Lombardi GA. QoS concept for packet oriented S-UMTS services. In: Proceedings of the 1st mobile summit, Thessaloniki, Greece; 2002.
[4] Baker, K.R.; Cole Smith, J., A multiple-criterion model for machine scheduling, Journal of scheduling, 6, 7-16, (2003) · Zbl 1154.90406
[5] Agnetis, A.; Mirchandani, P.B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations research, 229-242, (2004) · Zbl 1165.90446
[6] Yuan, J.; Shang, W.; Feng, Q., A note on the scheduling with two families of jobs, Journal of scheduling, 8, 537-542, (2005) · Zbl 1123.90040
[7] Cheng, T.C.E.; Ng, C.; Yuan, J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoretical computer science, 362, 273-281, (2006) · Zbl 1100.68007
[8] Ng, C.; Cheng, T.C.E.; Yuan, J., A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of combinatorial optimization, 12, 387-394, (2006) · Zbl 1126.90027
[9] Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of operations research, 150, 3-15, (2007) · Zbl 1144.90375
[10] Cheng, T.C.E.; Ng, C.; Yuan, J., Multi-agent scheduling on a single machine with MAX-form criteria, European journal of operational research, 188, 603-609, (2008) · Zbl 1129.90023
[11] Agnetis, A.; de Pascale, G.; Pacciarelli, D.A., Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of scheduling, 12, 401-415, (2009) · Zbl 1185.90063
[12] Lee, K.; Choi, B.C.; Leung, J.Y.T.; Pinedo, M.L., Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Information processing letters, 109, 913-917, (2009) · Zbl 1205.68516
[13] Leung, J.Y.T.; Pinedo, M.; Wan, G., Competitive two-agent scheduling and its applications, Operations research, 58, 458-469, (2010) · Zbl 1233.90163
[14] Mor, B.; Mosheiov, G., Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European journal of operational research, 206, 540-546, (2010) · Zbl 1188.90103
[15] Wright, T.P., Factors affecting the cost of airplanes, Journal of aeronautical science, 3, 122-128, (1936)
[16] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[17] Cheng, T.C.E.; Wang, G., Single machine scheduling with learning effect considerations, Annals of operations research, 98, 273-290, (2000) · Zbl 0967.68019
[18] Mosheiov, G., Scheduling problems with a learning effect, European journal of operational research, 132, 687-693, (2001) · Zbl 1017.90051
[19] Mosheiov, G.; Sidney, J.B., Scheduling with general job-dependent learning curves, European journal of operational research, 147, 665-670, (2003) · Zbl 1037.90529
[20] Bachman, A.; Janiak, A., Scheduling jobs with position-dependent processing times, Journal of the operational research society, 55, 257-264, (2004) · Zbl 1095.90033
[21] Kuo, W.H.; Yang, D.L., Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect, European journal of operational research, 174, 1184-1190, (2006) · Zbl 1103.90341
[22] Koulamas, C.; Kyparisis, G.J., Single-machine and two-machine flowshop scheduling with general learning functions, European journal of operational research, 178, 402-407, (2007) · Zbl 1107.90018
[23] Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022
[24] Ghodratnama, A.; Rabbani, M.; Tavakkoli-Moghaddam, R.; Baboli, A., Solving a single-machine scheduling problem with maintenance, job deterioration and learning effect by simulated annealing, Journal of manufacturing systems, 29, 1-9, (2010)
[25] Janiak, A.; Rudek, R.L., A note on a makespan minimization problem with a multi-ability learning effect, Omega, 38, 213-217, (2010)
[26] Ji, M.; Cheng, T., Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information processing letters, 110, 460-463, (2010) · Zbl 1229.90061
[27] Koulamas, C., A note on single-machine scheduling with job-dependent learning effects, European journal of operational research, 207, 1142-1143, (2010) · Zbl 1206.90044
[28] Okolowski, D.; Gawiejnowicz, S., Exact and heuristic algorithms for parallel-machine scheduling with Dejong’s learning effect, Computers & industrial engineering, 59, 272-279, (2010)
[29] Toksari, D., A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs, Computers & operations research, 38, 1361-1365, (2011) · Zbl 1208.90080
[30] Wu, C.C.; Yin, Y.; Cheng, S.R., Some single-machine scheduling problems with a truncation learning effect, Computers & industrial engineering, 60, 790-795, (2011)
[31] Liu, P.; Zhou, X.; Tang, L., Two-agent single-machine scheduling with position-dependent processing times, The international journal of advanced manufacturing technology, 48, 325-331, (2010)
[32] Cheng, T.C.E.; Cheng, S.R.; Wu, W.H.; Hsu, P.H.; Wu, C.C., A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Computers & industrial engineering, 60, 534-541, (2011)
[33] Hardy, G.; Littlewood, J.; Polya, G., Inequalities, (1967), Cambridge University Press London · JFM 60.0169.01
[34] Holland, J.H., Adaptation in natural and artificial systems, (1975), University of Michigan Press Ann Arbor
[35] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley · Zbl 0721.68056
[36] Booker, L.B.; Goldberg, D.E.; Holland, J.H., Classifier systems and genetic algorithms, Artificial intelligence, 40, 235-282, (1989)
[37] Jog, P.; Suh, J.Y.; Van Gucht, D., Parallel genetic algorithms applied to the traveling salesman problem, SIAM journal on optimization, 4, 515-529, (1991) · Zbl 0754.90061
[38] Balakrishnan, P., Manufacturing cell formation using similarity coefficients and a parallel genetic TSP algorithm: formulation and comparison, Mathematical and computer modeling, 21, 61-73, (1995) · Zbl 0833.90052
[39] Iyer, S.K.; Saxena, B., Improved genetic algorithm for the permutation flowshop scheduling problem, Computers & operations research, 31, 593-606, (2004) · Zbl 1046.90028
[40] Ugur, A., Path planning on a cuboid using genetic algorithms, Information sciences, 178, 3275-3287, (2008) · Zbl 1154.68512
[41] Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A genetic algorithm for flow shop scheduling problems, Journal of the operational research society, 55, 830-835, (2004) · Zbl 1060.90035
[42] Beasley, D.; Martin, R.; Bull, D., An overview of genetic algorithms, Part 1, fundamentals. university computing, 15, 58, (1993)
[43] Chen, J.S.; Pan, J.C.H.; Lin, C.M., A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem, Expert systems with applications, 34, 570-577, (2008)
[44] 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)
[45] Falkenauer E, Bouffouix S. A genetic algorithm for job shop. In: Proceedings of the IEEE international conference on robotics and automation; 1991.
[46] Bean, J.C., Genetic algorithms and random keys for sequencing and optimization, ORSA journal of computing, 6, 154-160, (1994) · Zbl 0807.90060
[47] 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)
[48] Reeves, C., Heuristics for scheduling a single machine subject to unequal job release times, European journal of operational research, 80, 397-403, (1995)
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.