Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection
We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching machine, or rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. The...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | The Scientific World Journal |
| Online Access: | http://dx.doi.org/10.1155/2014/270942 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832562359279812608 |
|---|---|
| author | Juan Zou Cuixia Miao |
| author_facet | Juan Zou Cuixia Miao |
| author_sort | Juan Zou |
| collection | DOAJ |
| description | We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching machine, or rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of
the rejected jobs. First, we show that the problem is NP-hard in the ordinary sense. Then, we present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem. Furthermore, we provide an optimal O(nlogn) time algorithm for the case where jobs have identical release dates. |
| format | Article |
| id | doaj-art-8afd7180066e462f94d258e985b13d2e |
| institution | Kabale University |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-8afd7180066e462f94d258e985b13d2e2025-02-03T01:22:48ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/270942270942Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and RejectionJuan Zou0Cuixia Miao1School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, ChinaSchool of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, ChinaWe consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching machine, or rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs. First, we show that the problem is NP-hard in the ordinary sense. Then, we present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem. Furthermore, we provide an optimal O(nlogn) time algorithm for the case where jobs have identical release dates.http://dx.doi.org/10.1155/2014/270942 |
| spellingShingle | Juan Zou Cuixia Miao Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection The Scientific World Journal |
| title | Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection |
| title_full | Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection |
| title_fullStr | Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection |
| title_full_unstemmed | Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection |
| title_short | Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection |
| title_sort | parallel batch scheduling of deteriorating jobs with release dates and rejection |
| url | http://dx.doi.org/10.1155/2014/270942 |
| work_keys_str_mv | AT juanzou parallelbatchschedulingofdeterioratingjobswithreleasedatesandrejection AT cuixiamiao parallelbatchschedulingofdeterioratingjobswithreleasedatesandrejection |