×

Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs. (English) Zbl 1245.90034

Summary: Deteriorating jobs scheduling has received tremendous attention in the past two decades. However, the group technology has seldom been discussed. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem of minimizing the total weighted number of late jobs with deteriorating jobs and setup times. A branch-and-bound with several dominance properties and a lower bound is developed to solve this problem optimally. Computational results show that the proposed algorithm can solve instances up to 1500 jobs. In addition, statistical tests are conducted to investigate the impact of the parameters.

MSC:

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

References:

[1] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers and 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, 56-64 (1990) · Zbl 0717.90034
[3] Rachaniotis, N. P.; Pappis, C. P., Scheduling fire fighting tasks using the concept of deteriorating jobs, Canadian Journal of Forest Research, 36, 652-658 (2006)
[4] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 495-498 (1990) · Zbl 0703.90051
[5] 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
[6] 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
[7] 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
[8] Ji, M.; Cheng, T. C.E., An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan, Information Processing Letters, 102, 41-47 (2007) · Zbl 1184.68125
[9] Wang, J. B.; Ng, C. T.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Computers & Operations Research, 35, 2684-2693 (2008) · Zbl 1180.90143
[10] 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 & Operations Research, 36, 2111-2121 (2009) · Zbl 1179.90142
[11] Ji, M.; Cheng, T. C.E., An FPTAS for parallel-machine scheduling under a grade of service provision to minimize makespan, Information Processing Letters, 108, 171-174 (2008) · Zbl 1191.68102
[12] Cheng, T. C.E.; Wu, C. C.; Lee, W. C., Some scheduling problems with deteriorating jobs and learning effects, Computers & Industrial Engineering, 54, 972-982 (2008)
[13] Wang, J. B.; Wang, D.; Zhang, G. D., Single-machine scheduling problems with both deteriorating jobs and learning effects, Applied Mathematical Modelling, 34, 2831-2839 (2010) · Zbl 1201.90089
[14] Wang, J. B.; Wei, C. M., Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Applied Mathematics and Computation, 217, 8093-8099 (2011) · Zbl 1230.90103
[15] Yang, S. H.; Wang, J. B., Minimizing total weighted completion time in a two-machine flowshop scheduling under simple linear deterioration, Applied Mathematics and Computation, 217, 4819-4826 (2011) · Zbl 1230.90104
[16] Rudek, R., Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect, International Journal of Advanced Manufacturing Technology (2011)
[17] Zhao, C. L.; Tang, H. Y., Scheduling deteriorating jobs under disruption, International Journal of Production Economics, 125, 294-299 (2010)
[18] 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 (2010) · Zbl 1202.90149
[19] Zhang, X. G.; Yan, G. L., Single-machine group scheduling problems with deteriorated and learning effect, Applied Mathematics and Computation, 216, 1259-1266 (2010) · Zbl 1187.90147
[20] Wang, J. B.; Wang, J. J.; Ji, P., Scheduling jobs with chain precedence constraints and deteriorating jobs, Journal of the Operational Research Society, 62, 1765-1770 (2011)
[21] Rudek, A.; Rudek, R., A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Computers and Mathematics with Applications, 62, 1870-1878 (2011) · Zbl 1231.90211
[22] Lai, P. J.; Lee, W. C.; Chen, H. H., Scheduling with deteriorating jobs and past-sequence-dependent setup times, International Journal of Advanced Manufacturing Technology, 54, 737-741 (2011)
[23] Yin, Y. Q.; Xu, D. H., Some single-machine scheduling problems with general effects of learning and deterioration, Computers and Mathematics with Applications, 61, 100-108 (2011) · Zbl 1207.90060
[24] Wang, J. B.; Wang, M. Z., Single-machine scheduling with nonlinear deterioration, Optimization Letters, 6, 87-98 (2012) · Zbl 1259.90040
[25] Yin, Y. Q.; Liu, M.; Hao, J. H.; Zhou, M. C., Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics, Part A, 42, 192-200 (2012)
[26] Webster, S.; Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43, 692-703 (1995) · Zbl 0857.90062
[27] Allahverdi, A.; Gupta, J. N.D.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, The International Journal of Management Sciences, 27, 219-239 (1999)
[28] 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
[29] Wu, C. C.; Lee, W. C., Single-machine group-scheduling problems with deteriorating setup times and job-processing times, International Journal of Production Economics, 115, 128-133 (2008)
[30] Wang, J. B.; Lin, L.; Shan, F., Single machine group scheduling problems with deteriorating jobs, International Journal of Advanced Manufacturing Technology, 39, 808-812 (2008)
[31] Wang, J. B.; Gao, W. J.; Wang, L. Y.; Wang, D., Single machine group scheduling with general linear deterioration to minimize the makespan, International Journal of Advanced Manufacturing Technology, 43, 146-150 (2009)
[32] Wang, J. B.; Huang, X.; Wu, Y. B.; Ji, P., Group scheduling with independent setup times, ready times, and deteriorating job processing times, International Journal of Advanced Manufacturing Technology (2011)
[33] Wang, J. B.; Sun, L. Y., Single-machine group scheduling with decreasing linear deterioration setup times and job processing times, International Journal of Advanced Manufacturing Technology, 49, 765-772 (2010)
[34] Wei, C. M.; Wang, J. B., Single machine quadratic penalty function scheduling with deteriorating jobs and group technology, Applied Mathematical Modelling, 34, 3642-3647 (2010) · Zbl 1201.90090
[35] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York) · Zbl 0366.68041
[36] French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Ellis Horwood Ltd · Zbl 0479.90037
[37] Fisher, M. L., A dual algorithm for the one-machine scheduling problem, Mathematical Programming, 11, 229-251 (1976) · Zbl 0359.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. 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.