Spring 2005 Seminar Series

DATE: Thursday, April 7, 2005
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the Philip M. Morse Reading Room, E40-106

SPEAKER:
Michael Pinedo
Julius Schlesinger Professor of Operations Management
Leonard N. Stern School of Business
New York University

TITLE
Scheduling Orders in Dedicated and Flexible Machine Environments

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 or certain amounts of various different product types which can be produced concurrently. Each order has a release date and a weight and preemptions are not allowed. Each product type can be produced on a specific subset of the machines. Two extreme cases of this 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 identical and 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. We consider various objective functions. We discuss the cases that are solvable in polynomial time and present complexity proofs for the more general problems. We furthermore focus on heuristics and approximation algorithms and present an empirical comparison of the various algorithms. The conclusions from the empirical analysis provide insights into the trade-offs with regard to solution quality, speed, memory space, and implementation complexity.This work has been done jointly with Joseph Y-T Leung and Haibing Li from the Computer Science Department at New Jersey Institute of Technology.