Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint
This paper addresses a parallel-batch scheduling problem that incorporates transportation of raw materials or semifinished products before processing with waiting time constraint. The orders located at the different suppliers are transported by some vehicles to a manufacturing facility for further p...
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/356364 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850172435019595776 |
|---|---|
| author | Hua Gong Daheng Chen Ke Xu |
| author_facet | Hua Gong Daheng Chen Ke Xu |
| author_sort | Hua Gong |
| collection | DOAJ |
| description | This paper addresses a parallel-batch scheduling problem that incorporates transportation of raw materials or semifinished products before processing with waiting time constraint. The orders located at the different suppliers are transported by some vehicles to a manufacturing facility for further processing. One vehicle can load only one order in one shipment. Each order arriving at the facility must be processed in the limited waiting time. The orders are processed in batches on a parallel-batch machine, where a batch contains several orders and the processing time of the batch is the largest processing time of the orders in it. The goal is to find a schedule to minimize the sum of the total flow time and the production cost. We prove that the general problem is NP-hard in the strong sense. We also demonstrate that the problem with equal processing times on the machine is NP-hard. Furthermore, a dynamic programming algorithm in pseudopolynomial time is provided to prove its ordinarily NP-hardness. An optimal algorithm in polynomial time is presented to solve a special case with equal processing times and equal transportation times for each order. |
| format | Article |
| id | doaj-art-c77a4ca654d14ee79b7693077458cecf |
| institution | OA Journals |
| issn | 2356-6140 1537-744X |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | The Scientific World Journal |
| spelling | doaj-art-c77a4ca654d14ee79b7693077458cecf2025-08-20T02:20:06ZengWileyThe Scientific World Journal2356-61401537-744X2014-01-01201410.1155/2014/356364356364Parallel-Batch Scheduling and Transportation Coordination with Waiting Time ConstraintHua Gong0Daheng Chen1Ke Xu2College of Science, Shenyang Ligong University, Shenyang 100159, ChinaCollege of Science, Shenyang Ligong University, Shenyang 100159, ChinaCollege of Science, Shenyang Ligong University, Shenyang 100159, ChinaThis paper addresses a parallel-batch scheduling problem that incorporates transportation of raw materials or semifinished products before processing with waiting time constraint. The orders located at the different suppliers are transported by some vehicles to a manufacturing facility for further processing. One vehicle can load only one order in one shipment. Each order arriving at the facility must be processed in the limited waiting time. The orders are processed in batches on a parallel-batch machine, where a batch contains several orders and the processing time of the batch is the largest processing time of the orders in it. The goal is to find a schedule to minimize the sum of the total flow time and the production cost. We prove that the general problem is NP-hard in the strong sense. We also demonstrate that the problem with equal processing times on the machine is NP-hard. Furthermore, a dynamic programming algorithm in pseudopolynomial time is provided to prove its ordinarily NP-hardness. An optimal algorithm in polynomial time is presented to solve a special case with equal processing times and equal transportation times for each order.http://dx.doi.org/10.1155/2014/356364 |
| spellingShingle | Hua Gong Daheng Chen Ke Xu Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint The Scientific World Journal |
| title | Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint |
| title_full | Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint |
| title_fullStr | Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint |
| title_full_unstemmed | Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint |
| title_short | Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint |
| title_sort | parallel batch scheduling and transportation coordination with waiting time constraint |
| url | http://dx.doi.org/10.1155/2014/356364 |
| work_keys_str_mv | AT huagong parallelbatchschedulingandtransportationcoordinationwithwaitingtimeconstraint AT dahengchen parallelbatchschedulingandtransportationcoordinationwithwaitingtimeconstraint AT kexu parallelbatchschedulingandtransportationcoordinationwithwaitingtimeconstraint |