Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint
We consider a scheduling problem where a set of jobs are first processed on a machine with an unavailability interval and, then, delivered to the customer directly. We focus on an integrated schedule of production and distribution such that the sum of the maximum delivery time and total delivery cos...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2020/8625849 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832566085293965312 |
|---|---|
| author | Jing Fan |
| author_facet | Jing Fan |
| author_sort | Jing Fan |
| collection | DOAJ |
| description | We consider a scheduling problem where a set of jobs are first processed on a machine with an unavailability interval and, then, delivered to the customer directly. We focus on an integrated schedule of production and distribution such that the sum of the maximum delivery time and total delivery cost is optimized. We study two classes of processing machines in the production part. In the first class, the serial-batch machine, the processing time of a batch is the sum of the processing times of its jobs. In the second class, the parallel-batch machine, the processing time of a batch is the maximum processing time of the jobs contained in the batch. The machine has a fixed capacity, and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. Two patterns of job’s processing, i.e., resumable and non-resumable, are considered if it is interrupted by the unavailability interval on the machine. In the distribution part, there are sufficient vehicles with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We show that these four problems are NP-hard in the strong sense in which the jobs have the same processing times and arbitrary sizes, and we propose an approximation algorithm for solving these four problems. Moreover, we show that the performance ratio of the algorithm is 2 for the serial-batch machine setting, and the error bound is 71/99 for the parallel-batch machine setting. We also evaluate the performance of the approximation algorithm by the computational results. |
| format | Article |
| id | doaj-art-980308fd6497466685b0826827c76edc |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-980308fd6497466685b0826827c76edc2025-02-03T01:05:15ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2020-01-01202010.1155/2020/86258498625849Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability ConstraintJing Fan0College of Arts and Science, Shanghai Polytechnic University, Shanghai 201209, ChinaWe consider a scheduling problem where a set of jobs are first processed on a machine with an unavailability interval and, then, delivered to the customer directly. We focus on an integrated schedule of production and distribution such that the sum of the maximum delivery time and total delivery cost is optimized. We study two classes of processing machines in the production part. In the first class, the serial-batch machine, the processing time of a batch is the sum of the processing times of its jobs. In the second class, the parallel-batch machine, the processing time of a batch is the maximum processing time of the jobs contained in the batch. The machine has a fixed capacity, and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. Two patterns of job’s processing, i.e., resumable and non-resumable, are considered if it is interrupted by the unavailability interval on the machine. In the distribution part, there are sufficient vehicles with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We show that these four problems are NP-hard in the strong sense in which the jobs have the same processing times and arbitrary sizes, and we propose an approximation algorithm for solving these four problems. Moreover, we show that the performance ratio of the algorithm is 2 for the serial-batch machine setting, and the error bound is 71/99 for the parallel-batch machine setting. We also evaluate the performance of the approximation algorithm by the computational results.http://dx.doi.org/10.1155/2020/8625849 |
| spellingShingle | Jing Fan Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint Discrete Dynamics in Nature and Society |
| title | Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint |
| title_full | Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint |
| title_fullStr | Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint |
| title_full_unstemmed | Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint |
| title_short | Integrated Scheduling Problem on a Single Bounded Batch Machine with an Unavailability Constraint |
| title_sort | integrated scheduling problem on a single bounded batch machine with an unavailability constraint |
| url | http://dx.doi.org/10.1155/2020/8625849 |
| work_keys_str_mv | AT jingfan integratedschedulingproblemonasingleboundedbatchmachinewithanunavailabilityconstraint |