Abstract
Expert scheduling systems, which develop the schedule automatically on a real time basis, are able to respond to the changes of product demand in Flexible Manufacturing Systems (FMS). While developing an expert scheduling system, the most time-consuming and difficult step is knowledge acquisition, the process that elicits the knowledge from experts and transfers it into the knowledge base. A trace-driven knowledge acquisition (TDKA) method is proposed to extract the expertise from the schedules produced by expert schedulers. Three phases are involved in the TDKA process: data collection, data analysis, and rule evaluation. In data collection, the expert schedulers are identified and decisions made during the scheduling process are recorded as a trace. In data analysis, a set of scheduling rules is developed based on the trace. The rules are then evaluated in the last phase. If the resulting rules do not perform as well as the expert schedulers, the process returns to phase two and refines the rules. The whole process stops whenever the resulting rules perform at least as well as the expert schedulers. A circuit board production line is used to demonstrate the feasibility of the TDKA methodology. The scheduling rules perform much better than the expert schedulers from whom the rules are extracted.
Similar content being viewed by others
References
Bainbridge, L. (1979) Verbal reports as evidence of the process operator's knowledge.International Journal of Man-Machine Studies 11, 411–36.
Cheeseman, P. (1984) Learning of expert systems from data.IEEE Workshop on Principles of Knowledge Based Systems, December, 115–22.
Collins, H. M. (1985)Changing Order: Replication and Induction in Scientific Practice, London: Sage.
Delgrande, J. P. (1987) A formal approach to learning from examples.International Journal of Man-Machine Studies 26, 123–41.
Dietterich, T. G. and Michalski, R. S. (1985) Discovering patterns in sequences of events.Artificial Intelligence 25, 187–232.
Ericsson, K. A. and Simon, H. A. (1984)Protocol Analysis: Verbal reports as Data, Massachusetts: The MIT Press.
Gafarian, A. V. and Walsh, J. E. (1970) Methods for statistical validation of a simulation model for freeway traffic near an on-ramp.Transportation Research 4, 379–84.
Gevarter, W. B. (1983) Expert systems: limited but powerful.IEEE Spectrum Aug., 39–45.
Hart, A. (1985) The role of induction in knowledge elicitation.Expert Systems 2, 24–8.
Hart, A. (1986)Knowledge Acquisition for Expert Systems. New York: McGraw-Hill.
Hawkins, D. (1983) An analysis of expert thinking.International Journal of Man-Machine Studies 18, 1–47.
Hedrick, C. L. (1976) Learning production systems from examples.Artificial Intelligence 7, 21–49.
Hodgson, T. J., King, R. E., Monteith, S. K. and Schultz, S. R. (1987) Developing control rules for AGVs using Markov decision processes.Material Flow 4, 85–96.
Kolokouris, A. T. (1986) Machine learning.Byte November, 225–31.
Law, A. M. and Kelton, W. D. (1982)Simulation Modeling and Analysis. New York: McGraw-Hill.
Lei, L. (1988) A State Dependent Approach to Supervisory Control of Robots. Ph. D. Thesis. University of Wisconsin-Madison, USA.
Michalski, R. S. and Chilausky, R. L. (1980) Knowledge acquisition by encoding expert rules versus computer induction form examples: a case study involving soybean pathology.International Journal of Man-Machine Studies 12, 63–87.
Naylor, T. H. and Finger, J. M. (1967) verification of computer simulation models.Management Science 14, 92–101.
Nisbett, R. E. and Wilson, T. D. (1977) Telling more than we can know: verbal reports on mental processes.Psychological Review 84, 231–59.
Quinlan, J. R. (1979) Discovering rules by induction from large collections of examples, inExpert System in the Microelectronic Age, pp. 168–201., Michie, D. (Ed) Edinburgh: Edinburgh University Press.
Rendell, L. (1983) A new basic for state-space learning systems and a successful implementation.Artificial Intelligence 20, 369–92.
Rendell, L., Benedict, P. and Cho, H. (1987) Concept acquisition from examples: measurement of system performance and suggestions for improved design.Technical Report UIUCDCS-R-87-1315, University of Illinois at Urbana-Champaign.
Thesen, A. and Lei, L. (1986) An expert system for scheduling robots in a flexible electroplating system with dynamically changing workloads, inProceedings of the Second ORSA/TIMS Conference on FMS: Operations Research Models and Applications, pp. 555–66.
Thompson, B. and Thompson, W. (1986) Finding rules in data.Byte November, 149–58.
Van Horn, R. L. (1971) Validation of simulation results.Management Science 17, 247–58.
VanLehn, K. (1987) Learning one subprocedure per lesson.Artificial Intelligence 31, 1–40.
Waterman, D. A. and Newell, A. (1971) Protocol analysis as a task for Artificial Intelligence.Artificial Intelligence 2, 285–318.
Weiss, S. M. and Kulikowski, C. A. (1984)A Practical Guide to Designing Expert Systems. New Jersey: Rowman and Allanheld.
Winston, P. H. (1982) Learning new principles from precedents and exercises.Artificial Intelligence 19, 321–50.
Yih, Y. (1988) Trace-driven Knowledge Acquisition for Expert Scheduling System. Ph.D. Thesis, University of Wisconsin-Madison. Madison, USA.
Yih, Y. and Thesen, A. (1989) An evaluation of user interfaces for interactive knowledge acquisition for expert scheduling systems, inProceedings of the Third International Conference on Human-Computer Interaction, pp. 720–26, Boston: Massachusetts.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Yih, Y. Trace-driven knowledge acquisition (TDKA) for rule-based real time scheduling systems. J Intell Manuf 1, 217–229 (1990). https://doi.org/10.1007/BF01471188
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01471188