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 time-and-resource-dependent processing times. (English) Zbl 1236.90059
Summary: We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.

90B35Scheduling theory, deterministic
Full Text: DOI
[1] Pinedo, M.: Scheduling: theory, algorithms, and systems, (2002) · Zbl 1145.90394
[2] Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing processing times: review and extensions, Journal of the operational research society 50, 711-720 (1999) · Zbl 1054.90542
[3] 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
[4] Wang, J. -B.; Xia, Z. -Q.: Scheduling jobs under decreasing linear deterioration, Information processing letters 94, 63-69 (2005) · Zbl 1182.68359 · doi:10.1016/j.ipl.2004.12.018
[5] Gawiejnowicz, S.; Kurc, W.; Pankowska, L.: Pareto and scalar bicriterion optimization in scheduling deteriorating jobs, Computers and operations research 33, 746-767 (2006) · Zbl 1116.90045 · doi:10.1016/j.cor.2004.07.016
[6] Janiak, A.; Kovalyov, M. Y.: Scheduling in a contaminated area: a model and polynomial algorithms, European journal of operational research 173, 125-132 (2006) · Zbl 1125.90354 · doi:10.1016/j.ejor.2004.12.012
[7] Wu, C. -C.; Lee, W. -C.: Two-machine flowshop scheduling to minimize mean flow time under linear deterioration, International journal of production economics 103, 572-584 (2006)
[8] Gawiejnowicz, S.: Scheduling deteriorating jobs subject to job or machine availability constraints, European journal of operational research 180, 472-478 (2007) · Zbl 1114.90034 · doi:10.1016/j.ejor.2006.04.021
[9] Wang, J. -B.; Ng, C. T.; Cheng, T. C. E.: Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Computers and operations research 35, 2684-2693 (2008) · Zbl 1180.90143 · doi:10.1016/j.cor.2006.12.026
[10] Lee, W. -C.; Wu, C. -C.; Wen, C. -C.; Chung, Y. -H.: A two-machine flowshop makespan scheduling problem with deteriorating jobs, Computers & industrial engineering 54, 737-749 (2008)
[11] 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 & industrial engineering 36, 2111-2121 (2009) · Zbl 1179.90142 · doi:10.1016/j.cor.2008.07.008
[12] Li, Y.; Li, G.; Sun, L.; Xu, Z.: Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times, International journal of production economics 118, 424-429 (2009)
[13] Tang, L.; Liu, P.: Two-machine flowshop scheduling problems involving a batching machine with transportation or deterioration consideration, Applied mathematical modelling 33, 1187-1199 (2009) · Zbl 1168.90473 · doi:10.1016/j.apm.2008.01.013
[14] 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, Computers and operations research 37, 83-90 (2010) · Zbl 1171.90404 · doi:10.1016/j.cor.2009.03.019
[15] 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 (2011) · Zbl 1202.90149 · doi:10.1016/j.amc.2010.08.064
[16] Yang, S. -H.; Wang, J. -B.: Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration, Applied mathematics and computation 217, 4819-4826 (2011) · Zbl 1230.90104 · doi:10.1016/j.amc.2010.11.037
[17] Huang, X.; Wang, M. -Z.: Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties, Applied mathematical modelling 35, 1349-1353 (2011) · Zbl 1211.90085 · doi:10.1016/j.apm.2010.09.013
[18] Wang, J. -B.; Wang, M. -Z.: Single-machine scheduling with nonlinear deterioration, Optimization letters (2010)
[19] Wang, J. -B.; Wang, J-J.; Ji, P.: Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the operational research society (2010)
[20] Gawiejnowicz, S.: Time-dependent scheduling, (2008) · Zbl 1155.90004
[21] Janiak, A.: Time-optimal control in a single machine problem with resource constraints, Automatica 22, 745-747 (1986) · Zbl 0608.90044 · doi:10.1016/0005-1098(86)90014-2
[22] Nowicki, E.; Zdrzalka, S.: A survey of results for sequencing problems with controllable processing times, Discrete applied mathematics 26, 271-287 (1990) · Zbl 0693.90056 · doi:10.1016/0166-218X(90)90105-L
[23] Panwalkar, S. S.; Rajagopalan, R.: Single machine sequencing with controllable processing times, European journal of operational research 59, 298-302 (1992) · Zbl 0760.90058 · doi:10.1016/0377-2217(92)90144-X
[24] Cheng, T. C. E.; Janiak, A.: Resource optimal control in some single machine scheduling problem, IEEE transactions on automatic control 39, 1243-1246 (1994) · Zbl 0816.90080 · doi:10.1109/9.293187
[25] Blazewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; Weglarz, J.: Scheduling computer and manufacturing processes, (2001)
[26] Wang, J. -B.; Xia, Z. -Q.: Single machine scheduling problems with controllable processing times and total absolute differences penalties, European journal of operational research 177, 638-645 (2007) · Zbl 1109.90045 · doi:10.1016/j.ejor.2005.10.054
[27] Tseng, C. -T.; Liao, C. -T.; Huang, K. -L.: Minimizing total tardiness on a single machine with controllable processing times, Computers and operations research 36, 1852-1858 (2009) · Zbl 1179.90159 · doi:10.1016/j.cor.2008.05.009
[28] A. Bachman, A. Janiak, Scheduling deteriorating jobs dependent on resources for the makespan minimization, Operations Research Proceedings 2000: Selected Papers of the Symposium on Operations Research (OR 2000), Dresden, (2000) 29-34. · Zbl 1021.90023
[29] Janiak, A.; Iwanowski, D.: Optimal resource allocation for single-machine scheduling problems with time and resource dependent processing times, Systems science 28, 85-94 (2002)
[30] Zhao, C. -L.; Zhang, Q. -L.; Tang, H. -Y.: Single machine scheduling with linear processing times, Acta automatica sinica 29, 703-708 (2003)
[31] Zhao, C. -L.; Tang, H. -Y.: Single machine scheduling problems with deteriorating jobs, Applied mathematics and computation 161, 865-874 (2005) · Zbl 1087.90033 · doi:10.1016/j.amc.2003.12.073
[32] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics 5, 287-326 (1979) · Zbl 0411.90044
[33] Kanet, J. J.: Minimizing variation of flow time in single machine systems, Management science 27, 1453-1459 (1981) · Zbl 0473.90048 · doi:10.1287/mnsc.27.12.1453
[34] Bagchi, U. B.: Simultaneous minimization of mean and variation of flow-time and waiting time in single machine systems, Operations research 37, 118-125 (1989) · Zbl 0661.90046 · doi:10.1287/opre.37.1.118