Integrated scheduling of production and distribution for manufacturers with parallel batching facilities |
| |
Authors: | Bayi Cheng Jun Pei Kai Li Panos M Pardalos |
| |
Institution: | 1.School of Management,Hefei University of Technology,Hefei,People’s Republic of China;2.Key Laboratory of Process Optimization and Intelligent Decision-Making, Ministry of Education,Hefei,People’s Republic of China;3.Center for Applied Optimization, Department of Industrial and Systems Engineering,University of Florida,Gainesville,USA |
| |
Abstract: | We consider a class of integrated scheduling problems for manufacturers. The manufacturer processes job orders and delivers products to the customer. The objective is to minimize the service span, that is, the period lasting from the time when the order is received to the time when all the products have been delivered to the customer. In the production phase, parallel batch-processing facilities are used to process the jobs. Jobs have arbitrary sizes and processing times. Each facility has a fixed capacity and jobs are processed in batches with the restriction that the total size of jobs in a batch does not exceed the facility capacity. When all the jobs in a batch are completed, the batch is completed. In the distribution phase, the manufacturer uses a vehicle with a fixed capacity to deliver products. The transportation time from the manufacturer to the customer is a constant. Completed products can be delivered in one transfer if the total size does not exceed the vehicle capacity. We first consider the problem where jobs have the same size and arbitrary processing times. We propose approximation algorithms for the problem and we show that a worst-case ratio performance guarantee is respectively 2–1/m. Then we consider the problem where jobs have the same processing time and arbitrary sizes. An approximation algorithm is proposed with an absolute worst-case ratio of 13/7 and an asymptotic worst-case ratio of 11/9. Both the proposed algorithms can be executed in polynomial time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|