×
Gawiejnowicz, Stanisław; Lin, Bertrand M. T.

Scheduling time-dependent jobs under mixed deterioration. (English) Zbl 1188.90095

Appl. Math. Comput. 216, No. 2, 438-447 (2010).
Summary: We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and \(\mathcal{NP}\)-hard cases.

Cited in 9 Documents

MSC:

90B35 Deterministic scheduling theory in operations research

Keywords:

single machine; polynomial-time algorithms; \(\mathcal{NP}\)-hard problems
PDF BibTeX XML Cite
\textit{S. Gawiejnowicz} and \textit{B. M. T. Lin}, Appl. Math. Comput. 216, No. 2, 438--447 (2010; Zbl 1188.90095)
Full Text: DOI

References:

[1] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading · Zbl 1058.90500
[2] 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
[3] Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent scheduling times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023
[4] Gawiejnowicz, S., Time-Dependent Scheduling. Monographs in Theoretical Computer Science: An EATCS Series (2008), Springer: Springer Berlin-New York · Zbl 1155.90004
[5] Gupta, S. K.; Kunnathur, A. S.; Dandapani, K., Optimal repayment policies for multiple loans, Omega, 15, 323-330 (1987)
[6] Ho, K. I.J.; Leung, J. Y.T.; Wei, W. D., Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters, 48, 315-320 (1993) · Zbl 0942.68508
[7] Mosheiov, G., Scheduling jobs with step-deterioration: minimizing makespan on a single- and multi-machine, Computers and Industrial Engineering, 28, 869-879 (1995)
[8] Zhao, C. L.; Tang, H. Y., Single machine scheduling problems with deteriorating jobs, Applied Mathematics and Computation, 161, 865-874 (2005) · Zbl 1087.90033
[9] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences, Discrete Applied Mathematics, 154, 2150-2166 (2006) · Zbl 1113.90059
[10] Barketau, M. S.; Cheng, T. C.E.; Ng, C. T.; Kotov, V.; Kovalyov, M. Y., Batch scheduling of step deteriorating jobs, Journal of Scheduling, 11, 17-28 (2008) · Zbl 1168.90421
[11] Chung, Y. H.; Liu, H. C.; Wu, C. C.; Lee, W. C., A deteriorating jobs problem with quadratic function of job lateness, Computers and Industrial Engineering, 57, 1182-1186 (2009)
[12] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Equivalent time-dependent scheduling problems, European Journal of Operational Research, 196, 919-929 (2009) · Zbl 1176.90213
[13] Gawiejnowicz, S.; Kurc, W.; Pankowska, L., Conjugate problems in time-dependent scheduling, Journal of Scheduling, 12, 543-553 (2009) · Zbl 1176.90212
[14] Lee, W. C.; Shiau, Y. R.; Chen, S. K.; Wu, C. C., A two-machine flow shop scheduling problem with deteriorating jobs and blocking, International Journal of Production Economics, 124, 188-197 (2010)
[15] Qi, X. L.; Zhou, S. G.; Yuan, J. J., Single machine parallel-batch scheduling with deteriorating jobs, Theoretical Computer Science, 410, 830-836 (2009) · Zbl 1162.90015
[17] Zhao, C. L.; Tang, H. Y., Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34, 238-243 (2010) · Zbl 1185.90114
[18] Gawiejnowicz, S.; Kononov, A., Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European Journal of Operational Research, 200, 305-308 (2010) · Zbl 1183.90170
[19] Lodree, E. J.; Geiger, C. D., A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European Journal of Operational Research, 201, 644-648 (2010) · Zbl 1192.90076
[20] 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
[21] Zhu, V. C.Y.; Sun, L. Y.; Sun, L. H.; Li, X. H., Single-machine scheduling time-dependent jobs with resource-dependent ready times, Computers and Industrial Engineering, 58, 84-87 (2010)
[22] 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
[23] Gawiejnowicz, S.; Pankowska, L., Scheduling jobs with varying processing times, Information Processing Letters, 54, 173-175 (1995) · Zbl 0875.68421
[24] Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M., Scheduling Theory: Single-Stage Systems (1994), Kluwer: Kluwer Dordrecht · Zbl 0827.90079
[25] Rau, G., Minimizing a function of permutations of \(n\) integers, Operations Research, 19, 237-240 (1971) · Zbl 0214.18701
[26] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[27] Johnson, D. S., The NP-completeness column: an ongoing guide, Journal of Algorithms, 2, 393-405 (1982) · Zbl 0494.68047
[28] Bachman, A.; Janiak, A.; Kovalyov, M. Y., Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81, 81-84 (2002) · Zbl 1032.68019
[29] Kononov, A., Scheduling problems with linear increasing processing times, (Zimmermann, U.; etal., Operations Research 1996 (1997), Springer), 208-212 · Zbl 0918.90085
[30] Bachman, A.; Janiak, A., Minimizing maximum lateness under linear deterioration, European Journal of Operational Research, 126, 557-566 (2000) · Zbl 0976.90039
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.