Citation
Scheduling Orders In Dedicated And Flexible Machine Environments. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 471-484, 2005.
Paper
Abstract
We are interested in the problem of scheduling orders for different product types in a facility with a number of identical machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environment are of interest. In the first case, each product type can be produced by one and only one dedicated machine. In the second case, all machines are flexible so that each product type can be produced by any one of machines. In addition, in this case, when a machine 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 extreme cases 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 environment cases. We also present empirical comparisons of the various algorithms. The conclusions form the empirical analysis provide insights into the trade-offs with regard to solution quality, speed, memory space, and implementation complexity.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2005-471-484-P, author = {J. Y-T. Leung and H. Li and M. Pinedo},
title = {Scheduling Orders In Dedicated And Flexible Machine Environments},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {471--484},
note = {Paper},
abstract = {We are interested in the problem of scheduling orders for different product types in a facility with a number of identical machines in parallel. Each order asks for certain amounts of various different product types which can be produced concurently. Each product type can be produced on a subset of the machines. Two extreme cases of machine environment are of interest. In the first case, each product type can be produced by one and only one dedicated machine. In the second case, all machines are flexible so that each product type can be produced by any one of machines. In addition, in this case, when a machine 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 extreme cases 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 environment cases. We also present empirical comparisons of the various algorithms. The conclusions form the empirical analysis provide insights into the trade-offs with regard to solution quality, speed, memory space, and implementation complexity.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-471-484-P.pdf} }