Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint
In this paper, we explored the nonresumable deteriorating job scheduling with machine availability constraints and rejection. The research presented here has focused on two key issues. First, it is assumed that jobs have a different basic processing time and the same deterioration rate. The objectiv...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2025-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/jom/4623702 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849247752124366848 |
|---|---|
| author | Guanghua Wu Huan Liu Yongping Liang |
| author_facet | Guanghua Wu Huan Liu Yongping Liang |
| author_sort | Guanghua Wu |
| collection | DOAJ |
| description | In this paper, we explored the nonresumable deteriorating job scheduling with machine availability constraints and rejection. The research presented here has focused on two key issues. First, it is assumed that jobs have a different basic processing time and the same deterioration rate. The objective is to minimize the total completion times of the accepted jobs plus the total penalty of the rejected jobs. We present a pseudopolynomial-time dynamic programming exact algorithm and subsequently develop it into a fully polynomial-time approximation scheme for the case where machine disruptions occur only on one of the machines. Second, we consider the scheduling problem in which the actual processing time of the job is a proportional function of its starting time. The objective is to minimize the weighted sum of completion times of the accepted jobs plus the total penalty of the rejected jobs. We present an alternative fully polynomial-time approximation scheme for the case where machine disruptions occur only on one of the machines. |
| format | Article |
| id | doaj-art-8ca7fe8fb4044972923d7125ede3420d |
| institution | Kabale University |
| issn | 2314-4785 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-8ca7fe8fb4044972923d7125ede3420d2025-08-20T03:58:08ZengWileyJournal of Mathematics2314-47852025-01-01202510.1155/jom/4623702Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability ConstraintGuanghua Wu0Huan Liu1Yongping Liang2Center for Mathematics and PhysicsCenter for Mathematics and PhysicsCenter for Mathematics and PhysicsIn this paper, we explored the nonresumable deteriorating job scheduling with machine availability constraints and rejection. The research presented here has focused on two key issues. First, it is assumed that jobs have a different basic processing time and the same deterioration rate. The objective is to minimize the total completion times of the accepted jobs plus the total penalty of the rejected jobs. We present a pseudopolynomial-time dynamic programming exact algorithm and subsequently develop it into a fully polynomial-time approximation scheme for the case where machine disruptions occur only on one of the machines. Second, we consider the scheduling problem in which the actual processing time of the job is a proportional function of its starting time. The objective is to minimize the weighted sum of completion times of the accepted jobs plus the total penalty of the rejected jobs. We present an alternative fully polynomial-time approximation scheme for the case where machine disruptions occur only on one of the machines.http://dx.doi.org/10.1155/jom/4623702 |
| spellingShingle | Guanghua Wu Huan Liu Yongping Liang Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint Journal of Mathematics |
| title | Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint |
| title_full | Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint |
| title_fullStr | Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint |
| title_full_unstemmed | Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint |
| title_short | Parallel Machine Scheduling of Deteriorating Jobs With Rejection and An Availability Constraint |
| title_sort | parallel machine scheduling of deteriorating jobs with rejection and an availability constraint |
| url | http://dx.doi.org/10.1155/jom/4623702 |
| work_keys_str_mv | AT guanghuawu parallelmachineschedulingofdeterioratingjobswithrejectionandanavailabilityconstraint AT huanliu parallelmachineschedulingofdeterioratingjobswithrejectionandanavailabilityconstraint AT yongpingliang parallelmachineschedulingofdeterioratingjobswithrejectionandanavailabilityconstraint |