Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time |
| |
Authors: | Joseph Y-T Leung Haibing Li Michael Pinedo |
| |
Institution: | (1) Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, USA;(2) Lehman Brothers Inc., 1301 The Avenue of Americas, New York, NY 10019, USA;(3) Stern School of Business, New York University, 40 West Fourth Street, New York, NY 10012, USA |
| |
Abstract: | We are interested in the problem of scheduling orders for different product types in a facility with a number of machines
in parallel. Each order asks for certain amounts of various different product types which can be produced concurrently. Each
product type can be produced on a subset of the machines. Two extreme cases of machine environments are of interest. In the
first case, each product type can be produced on one and only one machine which is dedicated to that product type. In the
second case, all machines are identical and flexible; each product type can be produced by any one of the machines. Moreover,
when a machine in this case switches over from one product type to another, no setup is required. Each order has a release
date and a weight. Preemptions are not allowed. The objective is minimizing the total weighted completion time of the orders.
Even when all orders are available at time 0, both types of machine environments have been shown to be NP-hard for any fixed
number (≥2) of machines. This paper focuses on the design and analysis of approximation algorithms for these two machine environments.
We also present empirical comparisons of the various algorithms. The conclusions from the empirical analyses provide insights
into the trade-offs with regard to solution quality, speed, and memory space.
Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users.
This research is supported by the National Science Foundation through grants DMI-0300156 and DMI-0245603. |
| |
Keywords: | Order scheduling Total weighted completion time Approximation algorithms NP-hard |
本文献已被 SpringerLink 等数据库收录! |
|