Operations Research Transactions >
2021 , Vol. 25 >Issue 2: 104 - 114
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.02.008
Approximation scheme for rescheduling on a single machine with job delay and rejection
Received date: 2020-01-31
Online published: 2021-05-06
In this paper, we investigate a rescheduling problem with rejection on a single machine due to the disruption of job delay. In this problem, we are given a set of jobs that are available at time zero in the planning horizon to be processed on a single machine. Each job has its processing time and weight. Before the formal processing begins, an original schedule according to the shortest weighted processing time first order is given with the goal to minimize the total weighted completion time. Based on the original schedule, the promised due date for each job is also given. However, when the formal processing starts, some jobs are delayed, which creates a disruption to the original schedule. Thus, it is necessary to adjust the original schedule, i.e., rescheduling. To achieve a reasonable service level, we are allowed to reject some delayed jobs by paying the corresponding rejection costs. In the adjusted schedule, the overall objective function is to minimize the sum of the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the weighted penalty for the maximum tardiness of the accepted jobs, while keeping the maximum tardiness no more than the given upper bound. For this problem, we design a dynamic programming exact algorithm running in pseudo-polynomial time. Furthermore, we derive a fully polynomial time approximation scheme by using the sparse technique.
Key words: rescheduling; job rejection; job delay; dynamic programming; approximation scheme
Shanshan YU, Miaomiao JIN, Wenchang LUO . Approximation scheme for rescheduling on a single machine with job delay and rejection[J]. Operations Research Transactions, 2021 , 25(2) : 104 -114 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.02.008
| 1 | Bean J C , Birge J R , Mittenthal J , et al. Matchup scheduling with multiple resources, release dates and disruptions[J]. Operations Research, 1991, 39 (3): 470- 483. |
| 2 | Zweben M , Davis E , Daun B , et al. Scheduling and rescheduling with iterative repair[J]. IEEE Transactions on Systems, Man and Cybernetics, 1993, 23 (6): 1588- 1596. |
| 3 | Clausen J, Larsen J, Larsen A, et al. Disruption management-operations research between planning and execution[R]. Lyngby: Technical University of Denmark, 2001. |
| 4 | Yu G , Argüello M , Song G , et al. A new era for crew recovery at continental airlines[J]. Interfaces, 2003, 33 (1): 5- 22. |
| 5 | Thompson S , Nunez M , Garfinkel R , et al. Efficient short-term allocation and reallocation of patients to floors of a hospital during demand surges[J]. Operations Research, 2009, 57 (2): 261- 273. |
| 6 | Hall N G , Potts C N . Rescheduling for new orders[J]. Operations Research, 2004, 52 (3): 440- 453. |
| 7 | Yuan J , Mu Y . Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption[J]. European Journal of Operational Research, 2007, 182 (2): 936- 944. |
| 8 | Hall N G , Potts C N . Rescheduling for job unavailability[J]. Operations Research, 2010, 58 (3): 746- 755. |
| 9 | Liu Z X , Ro Y K . Rescheduling for machine disruption to minimize makespan and maximum lateness[J]. Journal of Scheduling, 2014, 17 (4): 339- 352. |
| 10 | Liu Z X , Lu L , Qi X T . Cost allocation in rescheduling with machine unavailable period[J]. European Journal of Operational Research, 2018, 266 (1): 16- 28. |
| 11 | Luo W C , Luo T B , Goebel R , et al. Rescheduling due to machine disruption to minimize the total weighted completion time[J]. Journal of Scheduling, 2018, 21 (5): 565- 578. |
| 12 | Wang D J , Liu F , Jin Y C . A multi-objective evolutionary algorithm guided by directed search for dynamic scheduling[J]. Computers & Operations Research, 2017, 79, 279- 290. |
| 13 | Wang D J , Yin Y Q , Cheng T C E . Parallel-machine rescheduling with job unavailability and rejection[J]. Omega, 2018, 81, 246- 260. |
| 14 | Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326. |
| 15 | Kan A H G R. Machine scheduling problems: classification, complexity and computations[D]. Amsterdam: University of Amsterdam, 1976. |
| 16 | Engels D W , Karger D R , Kolliopoulos S G , et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003, 49 (1): 175- 191. |
/
| 〈 |
|
〉 |