zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. (English) Zbl 1217.90103
Summary: In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier -- this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.

90B35Scheduling theory, deterministic
Full Text: DOI
[1] Gupta, J. N. D.; Gupta, S. K.: Single facility scheduling with nonlinear processing times, Comput. ind. Eng. 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, Eur. J. Oper. res. 47, No. 1, 56-64 (1990) · Zbl 0717.90034 · doi:10.1016/0377-2217(90)90089-T
[3] Browne, S.; Yechiali, U.: Scheduling deteriorating jobs on a single processor, Oper. res. 38, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[4] Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing times: review and extensions, J. oper. Res. soc. 50, 711-720 (1999) · Zbl 1054.90542
[5] Cheng, T. C. E.; Ding, Q.; Lin, B. M. T.: A concise survey of scheduling with time-dependent processing times, Eur. J. Oper. res. 152, 1-13 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[6] Gawiejnowicz, S.; Kurc, W.; Pankowska, L.: Pareto and scalar bicriterion optimization in scheduling deteriorating jobs, Comput. oper. Res. 33, 746-767 (2006) · Zbl 1116.90045 · doi:10.1016/j.cor.2004.07.016
[7] Ji, M.; He, Y.; Cheng, T. C. E.: Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theor. comput. Sci. 362, 115-126 (2006) · Zbl 1100.68009 · doi:10.1016/j.tcs.2006.06.006
[8] Gawiejnowicz, S.; Kurc, W.; Pankowska, L.: Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete appl. Math. 154, 2150-2166 (2006) · Zbl 1113.90059 · doi:10.1016/j.dam.2005.04.016
[9] Wu, C. C.; Lee, W. C.: Two-machine flowshop scheduling to minimize mean flow time under linear deterioration, Int. J. Prod. econ. 103, 572-584 (2006)
[10] Shiau, Y. R.; Lee, W. C.; Wu, C. C.; Chang, C. M.: Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration, Int. J. Adv. manuf. Technol. 34, 774-782 (2007)
[11] Kang, L.; Ng, C. T.: A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs, Int. J. Prod. econ. 109, 180-184 (2007)
[12] Gawiejnowicz, S.: Scheduling deteriorating jobs subject to job or machine availability constraints, Eur. J. Oper. res. 180, 472-478 (2007) · Zbl 1114.90034 · doi:10.1016/j.ejor.2006.04.021
[13] Wu, C. C.; Lee, W. C.; Shiau, Y. R.: Minimizing the total weighted completion time on a single machine under linear deterioration, Int. J. Adv. manuf. Technol. 33, 1237-1243 (2007)
[14] Raut, S.; Swami, S.; Gupta, J. N. D.: Scheduling a capacitated single machine with time deteriorating job values, Int. J. Prod. econ. 114, 769-780 (2008) · Zbl 1167.90516
[15] Lee, W. C.; Wu, C. C.; Chung, Y. H.: Scheduling deteriorating jobs on a single machine with release times, Comput. ind. Eng. 54, 441-452 (2008)
[16] 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, Comput. oper. Res. 36, 2111-2121 (2009) · Zbl 1179.90142 · doi:10.1016/j.cor.2008.07.008
[17] Biskup, D.; Herrmann, J.: Single-machine scheduling against due dates with past-sequence-dependent setup times, Eur. J. Oper. res. 191, No. 2, 587-592 (2008) · Zbl 1147.90010 · doi:10.1016/j.ejor.2007.08.028
[18] Wang, J. -B.; Guo, Q.: A due-date assignment problem with learning effect and deteriorating jobs, Appl. math. Model. 34, 309-313 (2010) · Zbl 1185.90099 · doi:10.1016/j.apm.2009.04.020
[19] Ng, C. T.; Wang, J. -B.; Cheng, T. C. E.; Liu, L. L.: A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs, Comput. oper. Res. 37, No. 1, 83-90 (2010) · Zbl 1171.90404 · doi:10.1016/j.cor.2009.03.019
[20] Cheng, T. C. E.; Gupta, J. N. D.; Wang, G.: A review of flowshop scheduling research with setup times, Prod. oper. Manage. 9, No. 3, 262-282 (2000)
[21] Allahverdi, A.; Gupta, J. N. D.; Aldowaisan, T.: A review of scheduling research involving setup considerations, Omega 27, 219-239 (1999)
[22] Allahverdi, A.; Ng, C. T.; Cheng, T. C. E.; Kovalyov, M. Y.: A survey of scheduling problems with setup times or costs, Eur. J. Oper. res. 187, No. 3, 985-1032 (2008) · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060
[23] Koulamas, C.; Kyparisis, G. J.: Single-machine scheduling with past-sequence-dependent setup times, Eur. J. Oper. res. 187, 1045-1049 (2008) · Zbl 1137.90498 · doi:10.1016/j.ejor.2006.03.066
[24] Wu, C. C.; Shiau, Y. R.; Lee, W. C.: Single-machine group scheduling problems with deterioration consideration, Comput. oper. Res. 35, 1652-1659 (2008) · Zbl 1211.90094 · doi:10.1016/j.cor.2006.09.008
[25] Wu, C. C.; Lee, W. C.: Single-machine group-scheduling problems with deteriorating setup times and job-processing times, Int. J. Prod. econ. 115, 128-133 (2008)
[26] Lee, W. C.; Wu, C. C.: Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Appl. math. Model. 32, 362-373 (2008) · Zbl 1187.90134 · doi:10.1016/j.apm.2006.12.008
[27] Allahverdi, A.; Soroush, H. M.: The significance of reducing setup times/setup costs, Eur. J. Oper. res. 187, 978-984 (2008) · Zbl 1137.90475 · doi:10.1016/j.ejor.2006.09.010
[28] Eren, T.: A bicriteria parallel machine scheduling with a learning effect of setup and removal times, Appl. math. Model. 33, 1141-1150 (2009) · Zbl 1168.90436 · doi:10.1016/j.apm.2008.01.010
[29] Wang, J. -B.: Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect, Comput. ind. Eng. 55, No. 3, 584-591 (2008)
[30] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. discrete math. 5, 287-326 (1979) · Zbl 0411.90044