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)
Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs. (English) Zbl 1245.90034
Summary: Deteriorating jobs scheduling has received tremendous attention in the past two decades. However, the group technology has seldom been discussed. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem of minimizing the total weighted number of late jobs with deteriorating jobs and setup times. A branch-and-bound with several dominance properties and a lower bound is developed to solve this problem optimally. Computational results show that the proposed algorithm can solve instances up to 1500 jobs. In addition, statistical tests are conducted to investigate the impact of the parameters.
MSC:
90B35Scheduling theory, deterministic
References:
[1]Gupta, J. N. D.; Gupta, S. K.: Single facility scheduling with nonlinear processing times, Computers and industrial engineering 14, 387-393 (1988)
[2]Kunnathur, A. S.; Gupta, S. K.: Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European journal of operational research 47, 56-64 (1990) · Zbl 0717.90034 · doi:10.1016/0377-2217(90)90089-T
[3]Rachaniotis, N. P.; Pappis, C. P.: Scheduling fire fighting tasks using the concept of deteriorating jobs, Canadian journal of forest research 36, 652-658 (2006)
[4]Browne, S.; Yechiali, U.: Scheduling deteriorating jobs on a single processor, Operations research 38, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[5]Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing times: review and extensions, Journal of the operational research society 50, 711-720 (1999) · Zbl 1054.90542
[6]Cheng, T. C. E.; Ding, Q.; Lin, B. M. T.: A concise survey of scheduling with time-dependent processing times, European journal of operational research 152, 1-13 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[7]Wang, J. B.; Ng, C. T.; Cheng, T. C. E.; Liu, L. L.: Minimizing total completion time in a two-machine flow shop with deteriorating jobs, Applied mathematics and computation 180, 185-193 (2006) · Zbl 1104.90023 · doi:10.1016/j.amc.2005.11.162
[8]Ji, M.; Cheng, T. C. E.: An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information processing letters 102, 41-47 (2007) · Zbl 1184.68125 · doi:10.1016/j.ipl.2006.11.014
[9]Wang, J. B.; Ng, C. T.; Cheng, T. C. E.: Single-machine scheduling with deteriorating jobs under a series – parallel graph constraint, Computers & operations research 35, 2684-2693 (2008) · Zbl 1180.90143 · doi:10.1016/j.cor.2006.12.026
[10]Lee, W. C.; Wu, C. C.; Chung, Y. H.; Liu, H. C.: Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates, Computers & operations research 36, 2111-2121 (2009) · Zbl 1179.90142 · doi:10.1016/j.cor.2008.07.008
[11]Ji, M.; Cheng, T. C. E.: An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, Information processing letters 108, 171-174 (2008) · Zbl 1191.68102 · doi:10.1016/j.ipl.2008.04.021
[12]Cheng, T. C. E.; Wu, C. C.; Lee, W. C.: Some scheduling problems with deteriorating jobs and learning effects, Computers & industrial engineering 54, 972-982 (2008)
[13]Wang, J. B.; Wang, D.; Zhang, G. D.: Single-machine scheduling problems with both deteriorating jobs and learning effects, Applied mathematical modelling 34, 2831-2839 (2010) · Zbl 1201.90089 · doi:10.1016/j.apm.2009.12.017
[14]Wang, J. B.; Wei, C. M.: Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Applied mathematics and computation 217, 8093-8099 (2011) · Zbl 1230.90103 · doi:10.1016/j.amc.2011.03.010
[15]Yang, S. H.; Wang, J. B.: Minimizing total weighted completion time in a two-machine flowshop scheduling under simple linear deterioration, Applied mathematics and computation 217, 4819-4826 (2011) · Zbl 1230.90104 · doi:10.1016/j.amc.2010.11.037
[16]Rudek, R.: Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect, International journal of advanced manufacturing technology (2011)
[17]Zhao, C. L.; Tang, H. Y.: Scheduling deteriorating jobs under disruption, International journal of production economics 125, 294-299 (2010)
[18]Yang, S. J.: Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Applied mathematics and computation 217, 3321-3329 (2010) · Zbl 1202.90149 · doi:10.1016/j.amc.2010.08.064
[19]Zhang, X. G.; Yan, G. L.: Single-machine group scheduling problems with deteriorated and learning effect, Applied mathematics and computation 216, 1259-1266 (2010) · Zbl 1187.90147 · doi:10.1016/j.amc.2010.02.018
[20]Wang, J. B.; Wang, J. J.; Ji, P.: Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the operational research society 62, 1765-1770 (2011)
[21]Rudek, A.; Rudek, R.: A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Computers and mathematics with applications 62, 1870-1878 (2011) · Zbl 1231.90211 · doi:10.1016/j.camwa.2011.06.030
[22]Lai, P. J.; Lee, W. C.; Chen, H. H.: Scheduling with deteriorating jobs and past-sequence-dependent setup times, International journal of advanced manufacturing technology 54, 737-741 (2011)
[23]Yin, Y. Q.; Xu, D. H.: Some single-machine scheduling problems with general effects of learning and deterioration, Computers and mathematics with applications 61, 100-108 (2011) · Zbl 1207.90060 · doi:10.1016/j.camwa.2010.10.036
[24]Wang, J. B.; Wang, M. Z.: Single-machine scheduling with nonlinear deterioration, Optimization letters 6, 87-98 (2012)
[25]Yin, Y. Q.; Liu, M.; Hao, J. H.; Zhou, M. C.: Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE transactions on systems, man, and cybernetics, part A 42, 192-200 (2012)
[26]Webster, S.; Baker, K. R.: Scheduling groups of jobs on a single machine, Operations research 43, 692-703 (1995) · Zbl 0857.90062 · doi:10.1287/opre.43.4.692
[27]Allahverdi, A.; Gupta, J. N. D.; Aldowaisan, T.: A review of scheduling research involving setup considerations, omega, The international journal of management sciences 27, 219-239 (1999)
[28]Wu, C. C.; Shiau, Y. R.; Lee, W. C.: Single-machine group scheduling problems with deterioration consideration, Computers and operations research 35, 1652-1659 (2008) · Zbl 1211.90094 · doi:10.1016/j.cor.2006.09.008
[29]Wu, C. C.; Lee, W. C.: Single-machine group-scheduling problems with deteriorating setup times and job-processing times, International journal of production economics 115, 128-133 (2008)
[30]Wang, J. B.; Lin, L.; Shan, F.: Single machine group scheduling problems with deteriorating jobs, International journal of advanced manufacturing technology 39, 808-812 (2008)
[31]Wang, J. B.; Gao, W. J.; Wang, L. Y.; Wang, D.: Single machine group scheduling with general linear deterioration to minimize the makespan, International journal of advanced manufacturing technology 43, 146-150 (2009)
[32]Wang, J. B.; Huang, X.; Wu, Y. B.; Ji, P.: Group scheduling with independent setup times, ready times, and deteriorating job processing times, International journal of advanced manufacturing technology (2011)
[33]Wang, J. B.; Sun, L. Y.: Single-machine group scheduling with decreasing linear deterioration setup times and job processing times, International journal of advanced manufacturing technology 49, 765-772 (2010)
[34]Wei, C. M.; Wang, J. B.: Single machine quadratic penalty function scheduling with deteriorating jobs and group technology, Applied mathematical modelling 34, 3642-3647 (2010) · Zbl 1201.90090 · doi:10.1016/j.apm.2010.03.014
[35]Karp, R. M.: Reducibility among combinatorial problems, Complexity of computer computations (1972)
[36]French, S.: Sequencing and scheduling: an introduction to the mathematics of the job-shop, (1982) · Zbl 0479.90037
[37]Fisher, M. L.: A dual algorithm for the one-machine scheduling problem, Mathematical programming 11, 229-251 (1976) · Zbl 0359.90039 · doi:10.1007/BF01580393