This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hall, N. G. Articles by Posner, M. E. Search for Related Content

Generating Experimental Data for Computational Testing with Machine Scheduling Applications

Fisher College of Business, Department of Management Sciences, The Ohio State University, Columbus, Ohio 43210-1399
Department of Industrial and Systems Engineering, The Ohio State University, Columbus, Ohio 43210-1271
hall.33{at}osu.edu
posner.1{at}osu.edu

The operations research literature provides little guidance about how data should be generated for the computational testing of algorithms or heuristic procedures. We discuss several widely used data generation schemes, and demonstrate that they may introduce biases into computational results. Moreover, such schemes are often not representative of the way data arises in practical situations. We address these deficiencies by describing several principles for data generation and several properties that are desirable in a generation scheme. This enables us to provide specific proposals for the generation of a variety of machine scheduling problems. We present a generation scheme for precedence constraints that achieves a target density which is uniform in the precedence constraint graph. We also present a generation scheme that explicitly considers the correlation of routings in a job shop. We identify several related issues that may influence the design of a data generation scheme. Finally, two case studies illustrate, for specific scheduling problems, how our proposals can be implemented to design a data generation scheme.

Subject classifications: Simulation, random variable generation: methods for generating random data; Production/scheduling: experimental data for testing algorithms and heuristics.
History: Received February 1997; revision received October 1998; revision received April 2000; accepted June 2000.