×

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.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ · 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
[4] Wang, J.-B.; Xia, Z.-Q., Scheduling jobs under decreasing linear deterioration, Information Processing Letters, 94, 63-69 (2005) · Zbl 1182.68359
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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
[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), Springer: Springer Berlin, ISBN 978-3-540-69445-8 · 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
[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
[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
[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
[25] Blazewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling Computer and Manufacturing Processes (2001), Springer: Springer Berlin, Heidelberg · Zbl 0985.90033
[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
[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
[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.; 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) · Zbl 1498.90110
[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
[32] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., 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
[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
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.