Minimising mean tardiness with alternative operations in two-machine flow-shop scheduling

Abstract

This paper describes the development of a mixed binary integer programming (BIP) model for scheduling alternative operations in two-machine flow-shop problems with mean tardiness as the criterion. Although the mixed BIP model provides an optimal solution, its variables and constraints increase drastically as the number of jobs increases. Therefore, an optimal solution is not always attainable within the allowable time by solving the mixed BIP model. Consequently, two heuristics suitable for the formulated scheduling problems are proposed. Computational experiments are conducted to test the accuracy and efficiency of the heuristics in generating near optimal solutions for minimising the mean tardiness of jobs.

Keywords:

• Scheduling
• Two-machine flow-shop
• Alternative operations
• Tardiness

Acknowledgement

This research was supported by the National Science Council of Taiwan, Republic of China, under grant NSC-89-2213-E-269-001.

Jen-Shiang Chen is an Associate Professor in the Department of Industrial Engineering and Management, Far East College. He obtained his Ph.D. in Industrial Management from the National Taiwan University of Science and Technology. His current research interests include production scheduling and supply chain management. His recent publications have appeared in Journal of the Operational Research Society, Computers & Operations Research, Engineering Optimization, International Journal of Systems Science, International Journal of Industrial Engineering–Theory, Applications and Practice, etc.

Jason Chao-Hsien Pan is a Professor of Industrial Management at the National Taiwan University of Science and Technology. He completed his Ph.D. degree in Industrial Engineering from the University of Houston. His current research interests include production scheduling and inventory management. His recent publications have appeared in International Journal of Production Research, Journal of the Operational Research Society, Computers & Operations Research, International Journal of Systems Science, Production Planning & Control, etc.