Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection
We investigate the single-machine parallel-batch scheduling problem with nonidentical job sizes and rejection. In this problem, a set of jobs with different processing times and nonidentical sizes is given to be possibly processed on a parallel-batch processing machine. Each job is either accepted a...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-02-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/2/258 |
| _version_ | 1818536756156301312 |
|---|---|
| author | Miaomiao Jin Xiaoxia Liu Wenchang Luo |
| author_facet | Miaomiao Jin Xiaoxia Liu Wenchang Luo |
| author_sort | Miaomiao Jin |
| collection | DOAJ |
| description | We investigate the single-machine parallel-batch scheduling problem with nonidentical job sizes and rejection. In this problem, a set of jobs with different processing times and nonidentical sizes is given to be possibly processed on a parallel-batch processing machine. Each job is either accepted and then processed on the machine or rejected by paying its rejection penalty. Preemption is not allowed. Our task is to choose the accepted jobs and schedule them as batches on the machine to minimize the makespan of the accepted jobs plus the total rejection penalty of the rejected jobs. We provide an integer programming formulation to exactly solve our problem. Then, we propose three fast heuristic algorithms to solve the problem and evaluate their performances by using a small numerical example. |
| first_indexed | 2024-12-11T18:42:02Z |
| format | Article |
| id | doaj.art-d3158c10ab5947b5b3c7eb7484694fb5 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-12-11T18:42:02Z |
| publishDate | 2020-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d3158c10ab5947b5b3c7eb7484694fb52022-12-22T00:54:35ZengMDPI AGMathematics2227-73902020-02-018225810.3390/math8020258math8020258Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and RejectionMiaomiao Jin0Xiaoxia Liu1Wenchang Luo2School of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaSchool of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaSchool of Mathematics and Statistics, Ningbo University, Ningbo 315211, ChinaWe investigate the single-machine parallel-batch scheduling problem with nonidentical job sizes and rejection. In this problem, a set of jobs with different processing times and nonidentical sizes is given to be possibly processed on a parallel-batch processing machine. Each job is either accepted and then processed on the machine or rejected by paying its rejection penalty. Preemption is not allowed. Our task is to choose the accepted jobs and schedule them as batches on the machine to minimize the makespan of the accepted jobs plus the total rejection penalty of the rejected jobs. We provide an integer programming formulation to exactly solve our problem. Then, we propose three fast heuristic algorithms to solve the problem and evaluate their performances by using a small numerical example.https://www.mdpi.com/2227-7390/8/2/258parallel-batch schedulingsingle machinejob sizesrejectionmakespan |
| spellingShingle | Miaomiao Jin Xiaoxia Liu Wenchang Luo Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection Mathematics parallel-batch scheduling single machine job sizes rejection makespan |
| title | Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection |
| title_full | Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection |
| title_fullStr | Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection |
| title_full_unstemmed | Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection |
| title_short | Single-Machine Parallel-Batch Scheduling with Nonidentical Job Sizes and Rejection |
| title_sort | single machine parallel batch scheduling with nonidentical job sizes and rejection |
| topic | parallel-batch scheduling single machine job sizes rejection makespan |
| url | https://www.mdpi.com/2227-7390/8/2/258 |
| work_keys_str_mv | AT miaomiaojin singlemachineparallelbatchschedulingwithnonidenticaljobsizesandrejection AT xiaoxialiu singlemachineparallelbatchschedulingwithnonidenticaljobsizesandrejection AT wenchangluo singlemachineparallelbatchschedulingwithnonidenticaljobsizesandrejection |