zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.
MSC:
90B35Scheduling theory, deterministic
90C59Approximation methods and heuristics
68T05Learning and adaptive systems
References:
[1]Curiel, I.; Pederzoli, G.; Tijs, S.: Sequencing games, European journal of operational research 40, 344-351 (1989) · Zbl 0674.90107 · doi:10.1016/0377-2217(89)90427-X
[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 · doi:10.1007/BF01585572
[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.; Smith, J. Cole: A multiple-criterion model for machine scheduling, Journal of scheduling 6, 7-16 (2003) · Zbl 1154.90406 · doi:10.1023/A:1022231419049
[5]Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A.: Scheduling problems with two competing agents, Operations research, 229-242 (2004) · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[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 · doi:10.1007/s10951-005-4997-z
[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 · doi:10.1016/j.tcs.2006.07.011
[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 · doi:10.1007/s10878-006-9001-0
[9]Agnetis, A.; Pacciarelli, D.; Pacifici, A.: Multi-agent single machine scheduling, Annals of operations research 150, 3-15 (2007) · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y
[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 · doi:10.1016/j.ejor.2007.04.040
[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 · doi:10.1007/s10951-008-0098-0
[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 · doi:10.1016/j.ipl.2009.04.018
[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 · doi:10.1287/opre.1090.0744
[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 · doi:10.1016/j.ejor.2010.03.003
[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 · doi:10.1016/S0377-2217(98)00246-X
[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 · doi:10.1023/A:1019216726076
[18]Mosheiov, G.: Scheduling problems with a learning effect, European journal of operational research 132, 687-693 (2001) · Zbl 1017.90051 · doi:10.1016/S0377-2217(00)00175-2
[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 · doi:10.1016/S0377-2217(02)00358-2
[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 · doi:10.1057/palgrave.jors.2601689
[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 · doi:10.1016/j.ejor.2005.03.020
[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 · doi:10.1016/j.ejor.2006.01.030
[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 · doi:10.1016/j.ejor.2007.05.040
[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 · doi:10.1016/j.ejor.2010.06.022
[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 · doi:10.1016/j.cor.2010.12.010
[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)
[34]Holland, J. H.: Adaptation in natural and artificial systems, (1975)
[35]Goldberg, D. E.: Genetic algorithms in search, optimization, and machine learning, (1989) · 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 · doi:10.1137/0801031
[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 · doi:10.1016/0895-7177(95)00092-G
[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 · doi:10.1016/S0305-0548(03)00016-9
[40]Ugur, A.: Path planning on a cuboid using genetic algorithms, Information sciences 178, 3275-3287 (2008) · Zbl 1154.68512 · doi:10.1016/j.ins.2008.04.005
[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 · doi:10.1057/palgrave.jors.2601766
[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 · doi:10.1287/ijoc.6.2.154
[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)