Job Shop Scheduling with Set-up Times, Deadlines and Precedence Constraints*

Alkis Vazacopoulos
Dash Optimization, Englewood Cliffs, NJ

Abstract

In the last 15 years several procedures have been developed that can find
solutions of acceptable quality in reasonable computing time to Job Shop
Scheduling problems in environments that do not involve sequence dependent
setup times of machines. The presence of the latter, however, changes the
picture dramatically. In this paper we adapt one of the best known
heuristics, the Shifting Bottleneck Procedure, to the case when sequence
dependent setup times play an important role. This is done by treating the
single machine scheduling problems that arise in the process as traveling
salesman problems with time windows, and solving the latter by an efficient
dynamic programming algorithm. The model treated here also incorporates
precedence constraints, release times and deadlines. Computational
experience on a vast array of instances, mainly from the semiconductor
industry, shows our procedure to substantially advance the state of the art.


*joint work with
Egon Balas, Carnegie Mellon University
Neil Simonetti, Bryn Athyn College of the New Church, Bryn Athyn PA


Short Bio

Dr. Alkis Vazacopoulos is the President at Dash Optimization, Inc. where works
closely with OEMs/ISVs in developing optimization solutions. He also does consulting
work with Fortune 500 companies in the areas of finance, marketing optimization, data
mining, supply chain, procurement and decision analytics.
Dr. Vazacopoulos attended Florida International University and received an MS in
Management Information Systems. He then attended the Graduate School of Industrial
Administration at Carnegie Mellon University. In 1994 he completed his PhD in
Industrial Administration. He has a Bachelors degree from University of Piraeus
(Graduate School of Industrial Studies, 1986).
Dr. Vazacopoulos worked as an Associate Professor at Fairleigh Dickinson University
from 1994 to 2001 and now has Adjunct Professor status.
To keep in touch with academia, Dr.  Vazacopoulos gives seminars at different
universities including: University of Florida, Gainesville, Purdue University, University of
Texas-Austin, University of Paris, Imperial College.
Dr. Vazacopoulos is Associated Faculty at University of Florida (Department of
Industrial Engineering). He  is a regular Panelist at National Science Foundation.