We investigated a novel rescheduling problem in which the original jobs have already been scheduled on a single machine with the aim of minimizing either maximum lateness or maximum tardiness. Before the execution of this planned schedule, a set of new jobs arrives, making it necessary to reconsider the schedule. The decision-maker needs to determine a revised sequence for the original and new jobs while avoiding excessive disruption to the planned schedule. For original jobs, the extent of disruption is defined as the deviation of completion time between its planned and adjusted schedule. To preserve an adequate service level for the original jobs, one possible approach is to reject some new jobs by paying rejection costs. We proposed general models in which the maximum completion time deviation appears not only as a constraint but also as a part of the optimization objective. The overall optimization objective is to minimize the sum of three components: the scheduling objective (maximum lateness or maximum tardiness) of the adjusted schedule, which contains original jobs and accepted new jobs, the maximum disruption penalty, and the total rejection cost. Two pseudo-polynomial time dynamic programming exact algorithms were developed to provide optimal solutions. In addition, genetic algorithms were designed to handle the problem more efficiently. The performance of both methods was evaluated through numerical experiments.
Citation: Xuecong Xu, Shuaijing Yu, Wenchang Luo. Rescheduling involving due dates on a single machine due to the arrival of new jobs with rejection[J]. Journal of Industrial and Management Optimization, 2026, 22(9): 4315-4338. doi: 10.3934/jimo.2026151
We investigated a novel rescheduling problem in which the original jobs have already been scheduled on a single machine with the aim of minimizing either maximum lateness or maximum tardiness. Before the execution of this planned schedule, a set of new jobs arrives, making it necessary to reconsider the schedule. The decision-maker needs to determine a revised sequence for the original and new jobs while avoiding excessive disruption to the planned schedule. For original jobs, the extent of disruption is defined as the deviation of completion time between its planned and adjusted schedule. To preserve an adequate service level for the original jobs, one possible approach is to reject some new jobs by paying rejection costs. We proposed general models in which the maximum completion time deviation appears not only as a constraint but also as a part of the optimization objective. The overall optimization objective is to minimize the sum of three components: the scheduling objective (maximum lateness or maximum tardiness) of the adjusted schedule, which contains original jobs and accepted new jobs, the maximum disruption penalty, and the total rejection cost. Two pseudo-polynomial time dynamic programming exact algorithms were developed to provide optimal solutions. In addition, genetic algorithms were designed to handle the problem more efficiently. The performance of both methods was evaluated through numerical experiments.
| [1] |
J. C. Bean, J. R. Birge, J. Mittenthal, C. E. Noon, Matchup scheduling with multiple resources, release dates and disruptions, Oper. Res., 39 (1991), 470–483. https://doi.org/10.1287/opre.39.3.470 doi: 10.1287/opre.39.3.470
|
| [2] |
M. Zweben, E. Davis, B. Daun, M. J. Deale, Scheduling and rescheduling with iterative repair, IEEE Trans. Syst. Man Cybern., 23 (1993), 1588–1596. https://doi.org/10.1109/21.257756 doi: 10.1109/21.257756
|
| [3] | J. Clausen, J. Larsen, A. Larsen, J. Hansen, Disruption management–operations research between planning and execution, OR/MS Today, 28 (2001), 40–43. Available from: https://optimization-online.org/?p = 9178. |
| [4] |
G. Yu, M. Argüello, G. Song, S. M. McCowan, A. White, A new era for crew recovery at Continental Airlines, Interfaces, 33 (2003), 5–22. https://doi.org/10.1287/inte.33.1.5.12720 doi: 10.1287/inte.33.1.5.12720
|
| [5] |
K. Dahal, K. Al-Arfaj, K. Paudyal, Modelling generator maintenance scheduling costs in deregulated power markets, Eur. J. Oper. Res., 240 (2015), 551–561. https://doi.org/10.1016/j.ejor.2014.07.008 doi: 10.1016/j.ejor.2014.07.008
|
| [6] |
N. G. Hall, C. N. Potts, Rescheduling for new orders, Oper. Res., 52 (2004), 440–453. https://doi.org/10.1287/opre.1030.0101 doi: 10.1287/opre.1030.0101
|
| [7] |
N. G. Hall, C. N. Potts, Rescheduling for job unavailability, Oper. Res., 58 (2010), 746–755. https://doi.org/10.1287/opre.1090.0751 doi: 10.1287/opre.1090.0751
|
| [8] |
Z. Liu, Y. K. Ro, Rescheduling for machine disruption to minimize makespan and maximum lateness, J. Sched., 17 (2014), 339–352. https://doi.org/10.1007/s10951-014-0372-2 doi: 10.1007/s10951-014-0372-2
|
| [9] |
G. E. Vieira, J. W. Herrmann, E. Lin, Rescheduling manufacturing systems: A framework of strategies, policies, and methods, J. Sched., 6 (2003), 39–62. https://doi.org/10.1023/A:1022235519958 doi: 10.1023/A:1022235519958
|
| [10] |
D. Ouelhadj, S. Petrovic, A survey of dynamic scheduling in manufacturing systems, J. Sched., 12 (2009), 417–431. https://doi.org/10.1007/s10951-008-0090-8 doi: 10.1007/s10951-008-0090-8
|
| [11] |
I. R. Uhlmann, E. M. Frazzon, Production rescheduling review: Opportunities for industrial integration and practical applications, J. Manuf. Syst., 49 (2018), 186–193. https://doi.org/10.1016/j.jmsy.2018.10.004 doi: 10.1016/j.jmsy.2018.10.004
|
| [12] |
Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, L. Stougie, Multiprocessor scheduling with rejection, SIAM J. Discrete Math., 13 (2000), 64–78. https://doi.org/10.1137/S0895480196300522 doi: 10.1137/S0895480196300522
|
| [13] | S. Sengupta, Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection, in Algorithms and Data Structures, F. Dehne, J. R. Sack, M. Smid, Eds., Lecture Notes in Computer Science, vol. 2748, Springer, Berlin, Heidelberg, 2003, 79–90. https://doi.org/10.1007/978-3-540-45078-8_8 |
| [14] |
D. W. Engels, D. R. Karger, S. G. Kolliopoulos, S. Sengupta, R. N. Uma, J. Wein, Techniques for scheduling with rejection, J. Algorithms, 49 (2003), 175–191. https://doi.org/10.1016/S0196-6774(03)00078-6 doi: 10.1016/S0196-6774(03)00078-6
|
| [15] |
J. Ou, X. Zhong, Bicriteria order acceptance and scheduling with consideration of fill rate, Eur. J. Oper. Res., 262 (2017), 904–907. https://doi.org/10.1016/j.ejor.2017.04.036 doi: 10.1016/j.ejor.2017.04.036
|
| [16] |
D. Shabtay, The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost, Eur. J. Oper. Res., 233 (2014), 64–74. https://doi.org/10.1016/j.ejor.2013.08.013 doi: 10.1016/j.ejor.2013.08.013
|
| [17] |
F. T. Nobibon, R. Leus, Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment, Comput. Oper. Res., 38 (2011), 367–378. https://doi.org/10.1016/j.cor.2010.06.003 doi: 10.1016/j.cor.2010.06.003
|
| [18] |
S. Thevenin, N. Zufferey, M. Widmer, Metaheuristics for a scheduling problem with rejection and tardiness penalties, J. Sched., 18 (2015), 89–105. https://doi.org/10.1007/s10951-014-0395-8 doi: 10.1007/s10951-014-0395-8
|
| [19] |
S. A. Slotnick, Order acceptance and scheduling: A taxonomy and review, Eur. J. Oper. Res., 212 (2011), 1–11. https://doi.org/10.1016/j.ejor.2010.09.042 doi: 10.1016/j.ejor.2010.09.042
|
| [20] |
D. Shabtay, N. Gaspar, M. Kaspi, A survey on offline scheduling with rejection, J. Sched., 16 (2013), 3–28. https://doi.org/10.1007/s10951-012-0303-z doi: 10.1007/s10951-012-0303-z
|
| [21] |
D. J. Wang, F. Liu, Y. Jin, A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling, Comput. Oper. Res., 79 (2017), 279–290. https://doi.org/10.1016/j.cor.2016.04.024 doi: 10.1016/j.cor.2016.04.024
|
| [22] |
D. Wang, Y. Yin, T. C. E. Cheng, Parallel-machine rescheduling with job unavailability and rejection, Omega, 81 (2018), 246–260. https://doi.org/10.1016/j.omega.2018.04.008 doi: 10.1016/j.omega.2018.04.008
|
| [23] |
W. Luo, M. Jin, B. Su, G. Lin, An approximation scheme for rejection-allowed single-machine rescheduling, Comput. Ind. Eng., 146 (2020), 106574. https://doi.org/10.1016/j.cie.2020.106574 doi: 10.1016/j.cie.2020.106574
|
| [24] |
K. Fang, W. Luo, M. L. Pinedo, M. Jin, L. Lu, Rescheduling for new orders on a single machine with rejection, J. Oper. Res. Soc., 75 (2024), 346–360. https://doi.org/10.1080/01605682.2023.2197000 doi: 10.1080/01605682.2023.2197000
|
| [25] | Y. X. Ren, S. S. Yu, L. S. Tan, W. C. Luo, Rescheduling involving deliver times on a single machine due to the arrival of new jobs with rejection, J. Oper. Res. Soc. China, (2025), 1–18. https://doi.org/10.1007/s40305-025-00607-x |
| [26] |
R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5 (1979), 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X doi: 10.1016/S0167-5060(08)70356-X
|
| [27] |
M. Srinivas, L. M. Patnaik, Genetic algorithms: A survey, Computer, 27 (1994), 17–26. https://doi.org/10.1109/2.294849 doi: 10.1109/2.294849
|
 jimo-22-09-151-s001.pdf |
 |
Xuecong Xu, Shuaijing Yu, Wenchang Luo. Rescheduling involving due dates on a single machine due to the arrival of new jobs with rejection[J]. Journal of Industrial and Management Optimization, 2026, 22(9): 4315-4338. doi: 10.3934/jimo.2026151
DownLoad: