×

Some single-machine and flowshop scheduling problems with a non-linear deterioration function. (English) Zbl 1231.90205

Summary: The deteriorating job scheduling problems have received increasing attention recently. However, most researchers assume that the actual job processing time is a linear function of its starting time. In fact, in some situations, the deterioration rate might increase or decrease as time passes. For example, the temperature of the ingot in the rolling machine might drop at a slower pace as the surface cools down. Thus, the drop of the ingot temperature might have a decreasing rate. On the other hand, the time to control a fire might go dramatically as time passes, and the time to cease a fire might have an increasing rate. In this paper, we propose a new deteriorating model where the deterioration rate might be increasing or decreasing as time passes. Under the proposed model, we provide the optimal solutions for some single-machine problems and some flowshop problems.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers & 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, 1, 56-64 (1990) · Zbl 0717.90034
[3] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[4] Sundararaghavan, P. S.; Kunnathur, A., Single machine scheduling with start time dependent processing time: some solvable cases, European Journal of Operational Research, 78, 3, 394-403 (1994) · Zbl 0816.90088
[5] Chen, Z. L., A note on single-processor scheduling with time-dependent execution times, Operations Research Letters, 17, 127-129 (1995) · Zbl 0841.90072
[6] Cheng, T. C.E.; Ding, Q., The complexity of single machine scheduling with release times, Information Processing Letters, 65, 2, 75-79 (1998) · Zbl 1338.68096
[7] Bachman, A.; Cheng, T. C.E.; Janiak, A.; Ng, C. T., A Scheduling start time dependent jobs to minimize the total weighted completion time, Journal of the Operational Research Society, 53, 6, 688-693 (2002) · Zbl 1059.90063
[8] Ng, C. T.; Cheng, T. C.E.; Bachman, A., Three scheduling problems with deteriorating jobs to minimize the total completion time, Information Processing Letters, 81, 6, 327-333 (2002)
[9] Cheng, T. C.E.; Ding, Q., Single machine scheduling with step-deteriorating processing times, European Journal of Operational Research, 134, 623-630 (2001) · Zbl 0984.90014
[10] Cheng, T. C.E.; Ding, Q.; Kovalyov, M. Y.; Bachman, A.; Janiak, A., Scheduling jobs with piecewise linear decreasing processing times, Naval Research Logistics, 50, 6, 531-554 (2003) · Zbl 1043.90027
[11] Cheng, T. C.E.; Ding, Q., Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine, Computers and Operations Research, 30, 1, 51-62 (2003) · Zbl 1029.90028
[12] 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
[13] Wang, J. B.; Xia, Z. Q., Flow shop scheduling with deteriorating jobs under dominating machines, Omega, 34, 327-336 (2006) · Zbl 1090.90095
[14] Wu, C. C.; Lee, W. C.; Shiau, Y. R., Minimizing the total weighted completion time on a single machine under linear deterioration, The International Journal of Advanced Manufacturing Technology, 33, 1237-1243 (2007)
[15] 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
[16] Hsieh, Y. C.; Bricker, D. L., Scheduling linearly deteriorating jobs on multiple machines, Computers & Industrial Engineering, 32, 727-734 (1997)
[17] Hindi, K. S.; Mhlanga, S., Scheduling linearly deteriorating jobs on parallel machines: a simulated annealing approach, Production Planning & Control, 12, 76-80 (2001)
[18] Lee, W. C.; Wu, C. C., Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Applied Mathematical Modelling, 32, 362-373 (2008) · Zbl 1187.90134
[19] 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
[20] 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
[21] Zhao, C. L.; Tang, H. Y., Single machine scheduling problems with deteriorating jobs, Applied Mathematics and Computation, 161, 865-874 (2005) · Zbl 1087.90033
[22] 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)
[23] 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)
[24] Lee, W. C.; Wu, C. C., Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Applied Mathematical Modelling, 32, 362-373 (2008) · Zbl 1187.90134
[25] Leung, J. Y.T.; Ng, C. T.; Cheng, T. C.E., Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times, European Journal of Operational Research, 187, 1090-1099 (2008) · Zbl 1138.90396
[26] 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
[27] Low, C.; Hsua, C. J.; Su, C. T., Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration, Computers and Mathematics with Applications, 56, 257-265 (2008) · Zbl 1145.90389
[28] Wang, J.-B., Single machine scheduling with decreasing linear deterioration under precedence constraints, Computers and Mathematics with Applications, 58, 95-103 (2009) · Zbl 1189.90069
[29] Zhao, C.-l.; Tang, H.-Y., Single machine scheduling with general job-dependent ageing effect and maintenance activities to minimize makespan, Applied Mathematical Modelling, 34, 837-841 (2010) · Zbl 1185.90106
[30] Voutsinas, T. G.; Pappis, C. P., Scheduling jobs with values exponentially deteriorating over time, International Journal of Production Economics, 79, 163-169 (2002)
[31] Sun, L. H.; Sun, L. Y.; Cui, K.; Wang, J. B., A note on flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, European Journal of Operational Research, 200, 309-311 (2010) · Zbl 1183.90192
[32] Yang, S. J.; Yang, D. L., Minimizing the total completion time in single-machine scheduling with ageing/deteriorating effects and deteriorating maintenance activities, Computers and Mathematics with Applications, 60, 2161-2169 (2010) · Zbl 1205.90141
[33] 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
[34] Yin, Y.; Xu, D., Some single-machine scheduling problems with general effects of learning and deterioration, Computers and Mathematics with Applications, 61, 100-108 (2011) · Zbl 1207.90060
[35] Wang, J. B., Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan, International Journal of Advanced Manufacturing Technology, 48, 719-723 (2010)
[36] Wang, J.-B.; Wang, M. Z., Single machine multiple common due dates scheduling with learning Effects, Computers and Mathematics with Applications, 60, 2998-3002 (2010) · Zbl 1207.90059
[37] 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
[38] 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
[39] Wang, J. B.; Huang, X.; Wang, X. Y.; Yin, N.; Wang, L. Y., Learning effect and deteriorating jobs in the single machine scheduling problems, Applied Mathematical Modelling, 33, 3848-3853 (2009) · Zbl 1205.90137
[40] Wang, J. B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 34, 309-313 (2010) · Zbl 1185.90099
[41] Wang, J. B.; Sun, L. H.; Sun, L. Y., Scheduling jobs with an exponential sum-of-actual-processing-time-based learning effect, Computers and Mathematics with Applications, 60, 2673-2678 (2010) · Zbl 1205.90138
[42] J.B. Wang, J.J. Wang, P. Ji, Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the Operational Research Society (2010). doi:10.1057/jors.2010.120; J.B. Wang, J.J. Wang, P. Ji, Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the Operational Research Society (2010). doi:10.1057/jors.2010.120
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.