This paper describes a global job shop scheduling procedure that uses a genetic algorithm to find a good schedule. Unlike previously considered algorithms, this procedure has been implemented in the scheduling system for a manufacturing facility and has led to improved scheduling. This facility is a semiconductor test area. The test area is a job shop and has sequence‐dependent setup times at some operations. The concern of management is to meet their customer due dates and to increase throughput. This requires the coordination of many resources, a task beyond the ability of simple dispatching rules. We discuss a centralized procedure that can find a good schedule through the use of a detailed scheduling model and a genetic algorithm that searches over combinations of dispatching rules. We discuss our effort in developing a system that models the shop, creates schedules for the test area personnel, and makes a number of contributions to test area management.
AdamsJ.BalasE., and ZawackD. (1988), “The Shifting Bottleneck Procedure for Job Shop Scheduling,”Management Science, 34, 391–401.
2.
AdelsbergerH. H. and KanetJ. J. (1991), “The Leitstand‐A New Tool in Computer‐Integrated Manufacturing,”Production and Inventory Management, 32, No. 1, 43–48.
3.
AdlerL.FraimanN.KobackerE.PinedoM.PlotnicoffJ. C., and WuT.‐P. (1993), “BPSS: A Scheduling Support System for the Packaging Industry,”Operations Research, 41, No. 4, 641–648.
4.
BarnesJ. W. and ChambersJ. B. (1991), Solving the Job Shop Scheduling Problem Using Tabu Search, Technical Report OPR91–06, Graduate Program in Operations Research, University of Texas at Austin.
5.
BeanJ. C. (1994), “Genetics and Random Keys for Sequencing and Optimization,”ORSA Journal of Computing, 6, 154–160.
6.
BensanaE.BelG., and DuboisD. (1988), “OPAL: A Multi‐Knowledge‐Based System for Industrial Job‐Shop Scheduling,”International Journal of Production Research, 26, No. 5, 795–819.
7.
BhaskaranK. and PinedoM. (1991), “Dispatching” in Handbook of Industrial Engineering, SalvendyG., (ed.), J. Wiley, New York, Chapter 83.
8.
CernyV. (1985), “Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm,”Journal of Optimization Theory and Applications, 45, 41, 1985.
9.
Consilium, Inc. (1988), Short‐Interval Scheduling System User's Manual, Internal publication, Mountain View, CA.
10.
DavisL. (1985), “Job Shop Scheduling with Genetic Algorithms,” in Proceedings of an International Conference on Genetic Algorithms and their Applications, GrefenstetteJ., ed. Pittsburgh, Pennsylvania, pp. 136–140.
11.
DavisL. (ed.) (1991), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York.
12.
FaalandB. and SchmittT. (1993), “Cost‐Based Scheduling of Workers and Equipment in a Fabrication and Assembly Shop,”Operations Research, 41, No. 2, 253–268.
13.
FisherH. and ThompsonG. L. (1963), “Probabilistic Learning Combinations of Local Job‐Shop Scheduling Rules” in Industrial Scheduling, MuthJ. F. and ThompsonG. L. (eds.), Prentice‐Hall, Inc., Englewood Cliffs, NJ. pp. 225–251.
14.
FoxB. R. and McMahonM. B. (1990), “Genetic Operators for Sequencing Problems,”Planning and Scheduling Group, McDonnell Douglas Space Systems, Houston, TX.
15.
FoxB. R. and SmithS. F. (1984), “ISIS‐A Knowledge‐Based System for Factory Scheduling,”Expert Systems, 1, No. 1, 25–49.
16.
FryT. D.PhilipoomP. R., and BlackstoneJ. H. (1988), “A Simulation Study of Processing Time Dispatching Rules,”Journal of Operations Management, 7, 77–92.
17.
GlasseyC. R. and PetrakianR. G. (1989), The Use of Bottleneck Starvation Avoidance With Queue Pre‐dictions in Shop Floor Control, Research Report ESRC 89–23, University of California, Berkeley.
18.
GlasseyC. R. and ResendeM. G. C. (1988), “Closed‐Loop Job Release Control for Visi Circuit Manufacturing,”IEEE Transactions on Semiconductor Manufacturing, 1, 36–46.
19.
GloverF. (1977), “Heuristics for Integer Programming Using Surrogate Constraints,”Decision Sciences, 8, No. 1, 156–166.
20.
GoldbergD. E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison‐Wesley, Reading, MA.
21.
HackmanS. T. and LeachmanR. C. (1989), “A General Framework for Modeling Production,”Management Science, 35, No. 4, 478–495.
22.
HerrmannJ. W. and LeeC.‐Y. (1992), Three‐Machine Look‐Ahead Scheduling Problems, Research Report 92–23, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL.
23.
HerrmannJ. W. (1993), “Solving a Class Scheduling Problem With a Genetic Algorithm,” to appear in ORSA Journal of Computing.
24.
HollandJ. H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI.
25.
HungY.‐F. and LeachmanR. C. (1992), A Production Planning Methodology for Semiconductor Manufacturing Based on Iterative Simulation and Linear Programming Calculations, Report 92–26, Engineering Systems Research Center, University of California, Berkeley, CA.
26.
JacobsF. R. (1984), “OPT Uncovered: Concepts Behind the System,”Industrial Engineering, 16, No. 10, 32–41.
27.
KirkpatrickS.GelattC. D., and VecchiM. P. (1983), “Optimization by Simulated Annealing,”Science, 220, 671.
28.
Van LaarhovenP. J. M.AartsE. H. L., and LenstraJ. K. (1988), Job Shop Scheduling by Simulated Annealing, Report OS‐R8809, Centre for Mathematics and Computer Science. Amsterdam, The Netherlands.
29.
LeachmanR. C. (1993), “Modeling Techniques for Automated Production Planning in the Semiconductor Industry” in Optimization in Industry, CirianiT. A. and LeachmanR. C. (eds.), John Wiley & Sons Ltd.
30.
LeachmanR. C. and SohoniV. S., Automated Shift Scheduling as a Tool for Problem Identification and People Man agement in Semiconductor Factories, University of California, Berkeley, CA.
31.
LeachmanR. C.SolorzanoM., and GlasseyC. R. (1988), A Queue Management Policy for the Release of Factory Work Orders, Research Report 88–19, Engineering Systems Research Center, University of California at Berkeley.
32.
LeeC.‐Y. and HerrmannJ. W. (1993), A Three‐Machine Scheduling Problem With Look‐Behind Characteristics, Research Report 93–11, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL.
33.
LeeC.‐Y.Martin‐VegaL. A.UzsoyR., and HinchmanJ. (1993), “Implementation of a Decision Support System for Scheduling Semiconductor Testing Operations,”Journal of Electronic Manufacturing, 3, 121–131.
34.
LeeC.‐Y.UzsoyR., and Martin‐VegaL. A. (1992), “Efficient Algorithms for Scheduling Semiconductor Burn‐in Operations,”Operations Research, 40, No. 4, 764–775.
35.
LiepinsG. E. and HilliardM. R. (1989), “Genetic Algorithms: Foundations and Applications,”Annals of Operations Research, 21, 31–58.
36.
MatsuoH.SuhC. J., and SullivanR. S. (1988), Controlled Search Simulated Annealing for General Job Shop Scheduling Problem, Working Paper #03–04–88. Graduate School of Business, University of Texas, Austin, Texas.
37.
MonmaC. L. and PottsC. N. (1989), “On the Complexity of Scheduling With Batch Setup Times,”Operations Research, 37, No. 5, 798–804.
38.
MortonT. E. (1993), Heuristic Scheduling Systems, Graduate School of Industrial Administration, Carnegie Mellon University, John Wiley, New York.
39.
MortonT. E.LawrenceS. R.RajagopolanS., and KekreS. (1988), “SCHED‐STAR: A Price‐Based Shop Scheduling Module,”Journal of Manufacturing and Operations Management, 1, 131–181.
40.
NajmiA. and LozinskiC., Managing Factory Productivity Using Object‐Oriented Simulation for Setting Shift Production Targets in VLSI Manufacturing, University of California, Berkeley, CA.
41.
NakanoR. and YamadaT. (1991), “Conventional Genetic Algorithms for Job Shop Problems” in Proceedings of the Fourth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, Inc. San Diego, California, pp. 474–479.
42.
OwP. S. and SmithS. F. (1988), “Viewing Scheduling as an Opportunistic Problem‐Solving Process,”Annals of Operations Research, 12, 85–108.
43.
PanwalkerS. S. and IskanderW. (1977), “A Survey of Scheduling Rules,”Operations Research, 25, 45–61.
44.
SadehN. (1991), MICRO‐BOSS: A Micro‐Opportunistic Factory Scheduler, Center for Integrated Manufacturing Decision Systems, The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
45.
SmithS. F.FoxM. S., and OwP. S. (1986), “Constructing and Maintaining Detailed Production Plans: Investigations into the Development of Knowledge‐Based Factory Scheduling Systems,”AI Magazine, 7, No. 4, 45–61.
46.
StorerR. H.WuS. Y. D., and VaccariR. (1990), Local Search in Problem and Heuristic Space for Job Shop Scheduling, Working Paper, Department of Industrial Engineering, Lehigh University, Allentown, PA.
47.
StorerR. H. (1992), “New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling,”Management Science, 38, No. 10, 1495–1509.
48.
UzsoyR.LeeC.‐Y., and Martin‐VegaL. A. (1992a), “A Review of Production Planning and Scheduling Models in the Semiconductor Industry, Part I: System Characteristics, Performance Evaluation and Production Planning,”IIE Transactions, 24, 47–61.
49.
UzsoyR. (1992b), “Scheduling Semiconductor Test Operations: Minimizing Maximum Lateness and Number of Tardy Jobs on a Single Machine,”Naval Research Logistics, 39, 369–388.
50.
UzsoyR. (1993), “A Review of Production Planning and Scheduling Models in the Semiconductor Industry, part II: Shop Floor Control,”IIE Transactions, 26, (1994), pp. 44–55.
51.
UzsoyR. and HinchmanJ. (1991a), Scheduling Semiconductor Testing Operations: Optimization and Approx imation, Proceedings, Joint U.S.‐German Conference on New Directions for Operations Research in Manufacturing, Gaithersburg, MD, July 30–31. pp. 179–199.
52.
UzsoyR. and LeonardP. A. (1991b), “Production Scheduling Algorithms for a Semiconductor Test Facility,”IEEE Transactions on Semiconductor Manufacturing. 4, (1991), pp. 271–280.
53.
VepsalainenA. P. J. and MortonT. E. (1988), “Improving Local Priority Rules with Global Lead‐Time Estimates,”Journal of Manufacturing and Operations Management, 1, 102–118.
54.
WeinL. M. (1988), “Scheduling Semiconductor Wafer Fabrication,”IEEE Transactions on Semiconductor Manufacturing, 1, 115–130.
55.
WuS. D.StorerR. H., and ChangP.‐C. (1993), “One‐machine Rescheduling Heuristics with Efficiency and Stability as Criteria,”Computers and Operations Research, 20, No. 1, 1–14.
