Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine

Naval Research Logistics (NRL)Volume 39, Issue 3 p. 369-388 Article Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine Reha Uzsoy, Reha Uzsoy School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907Search for more papers by this authorChung-Yee Lee, Chung-Yee Lee Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611Search for more papers by this authorLouis A. Martin-Vega, Louis A. Martin-Vega Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611Search for more papers by this author Reha Uzsoy, Reha Uzsoy School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907Search for more papers by this authorChung-Yee Lee, Chung-Yee Lee Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611Search for more papers by this authorLouis A. Martin-Vega, Louis A. Martin-Vega Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611Search for more papers by this author First published: April 1992 https://doi.org/10.1002/1520-6750(199204)39:3<369::AID-NAV3220390307>3.0.CO;2-FCitations: 49AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract We examine a class of single-machine scheduling problems with sequence-dependent setup times that arise in the context of semiconductor test operations. We present heuristics for the problems of minimizing maximum lateness with dynamic arrivals and minimizing number of tardy jobs. We exploit special problem structure to derive worst-case error bounds. The special problem structure also enables us to derive dynamic programming procedures for the problems where all jobs are available simultaneously. References 1 Adams, J., Balas, E., and Zawack, D., "The Shifting Bottleneck Procedure for Job-Shop Scheduling", Management Science, 34 (3), 391–401 (1988). 10.1287/mnsc.34.3.391 Web of Science®Google Scholar 2 Baker, K. R., Introduction to Sequencing and Scheduling, Wiley, New York, 1974. Google Scholar 3 Baker, K. R., and Su, Z.-S., "Sequencing with Due Dates and Early Start Times to Minimize Maximum Tardiness", Naval Research Logistics Quarterly, 21, 171–176 (1974). 10.1002/nav.3800210112 Web of Science®Google Scholar 4 Carlier, J., "The One-Machine Sequencing Problem", European Journal of Operational Research, 11, 42–47 (1982). 10.1016/S0377-2217(82)80007-6 Web of Science®Google Scholar 5 Hall, L., and Shmoys, D., " Jackson's Rule for One-Machine Scheduling: Making a Good Heuristic Better", Research Report No. OR 199-89, Operations Research Center, Massachusetts Institute of Technology (August 1989). Google Scholar 6 Kise, H., Ibaraki, T., and Mine, H., "A Solvable Case of the One-Machine Scheduling Problem with Ready and Due Times", Operations Research, 26, 121–126 (1978). 10.1287/opre.26.1.121 Web of Science®Google Scholar 7 Kise, H., Ibaraki, T., and Mine, H., "Performance Analysis of Six Approximation Algorithms for the One-Machine Maximum Lateness Problem with Ready Times", Journal of the Operations Research Society of Japan, 22 (3), 205–223 (1979). Web of Science®Google Scholar 8 Kise, H., and Uno, M., "One-Machine Scheduling Problems with Earliest Start and Due Time Constraints", Mem. Kyoto Tech. Univ. Sci. Tech. 27, 25–34 (1978). Google Scholar 9 Lageweg, B. J., Lenstra, J. K., and Rinnooy Kan, A. H. G., "Minimizing Maximum Lateness on One Machine: Computational Experience and Some Applications", Statistica Neerlandica, 30, 25–41 (1976). 10.1111/j.1467-9574.1976.tb00264.x Google Scholar 10 Lageweg, B. J., Lawler, F. L., Lenstra, J. K., and Rinnooy Kan, A. H. G., "Computer Aided Complexity Classification of Deterministic Scheduling Problems", Research Report No. BW 138/81, Mathematisch Centrum, Amsterdam (1981). Google Scholar 11 Lawler, E. L., "Optimal Sequencing of a Single Machine Subject to Precedence Constraints", Management Science, 19, 544–546 (1973) 10.1287/mnsc.19.5.544 Web of Science®Google Scholar 12 Lawler, E. L., "Sequencing to Minimize the Weighted Number of Tardy Jobs", Rev. Francaise Automatique, Informatique et Recherche Operationelle, 10, 27–33 (1976). Web of Science®Google Scholar 13 Lawler, E. L., and Moore, J. M., "A Functional Equation and its Application to Resource Allocation and Sequencing Problems", Management Science, 16, 77–84 (1969). 10.1287/mnsc.16.1.77 Web of Science®Google Scholar 14 McMahon, G., and Florian, M., "On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness", Operations Research, 23, 475–482 (1975). 10.1287/opre.23.3.475 Web of Science®Google Scholar 15 Monma, C., and Potts, C. N., "On the Complexity of Scheduling with Batch Setup Times", Operations Research, 37, 798–804 (1989). 10.1287/opre.37.5.798 Web of Science®Google Scholar 16 Picard, J. C., and Queyranne, M., "The Time-Dependent Travelling Salesman Problem and its Application to the Tardiness Problem in One-Machine Scheduling", Operations Research, 26 (1), 86–110 (1978). 10.1287/opre.26.1.86 Web of Science®Google Scholar 17 Potts, C. N., and Van Wassenhove, L. N., "Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs", Management Science, 34, 843–858 (1988). 10.1287/mnsc.34.7.843 Web of Science®Google Scholar 18 Potts, C. N., "Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times", Operations Research, 28, 1436–1441 (1980). 10.1287/opre.28.6.1436 Web of Science®Google Scholar 19 Uzsoy, R., Martin-Vega, L. A., Lee, C.-Y., and Leonard, P. A., "Production Scheduling Algorithms for a Semiconductor Test Facility", IEEE Transactions on Semiconductor Manufacturing, 4, 270–280 (1991). 10.1109/66.97809 Web of Science®Google Scholar 20 Uzsoy, R., Lee, C. Y., Martin-Vega, L. A., and Hinchman, J., "Scheduling Semiconductor Testing Operations: Optimization and Approximation", in Proceedings of the Joint US-German Conference on New Directions for Operations Research in Manufacturing, Gaithersburg, MD, July 30-31, 1991, to be published. Google Scholar 21 Villarreal, F. J., and Bulfin, R. L., "Scheduling a Single Machine to Minimize the Weighted Number of Tardy Jobs", IIE Transactions, 15, 337–343 (1983). 10.1080/05695558308974657 Web of Science®Google Scholar Citing Literature Volume39, Issue3April 1992Pages 369-388 ReferencesRelatedInformation