Planning & Scheduling Benchmarks

Introduction

One of us (Barry) currently serves as benchmarks secretary of the AAAI Special Interest Group in Manufacturing while the other (Mark) has similar responsibilities within the AIAA, Artificial Intelligence Technical Committee. Together we are in the process of preparing a series of benchmark planning and scheduling problems for publication over the Internet. The first of these problems has been completed and is described in a separate document. In the future we hope to provide a variety of problems, all based upon real applications. Because of our limited access to industrial problems the selection of problems that we provide will be limited, but we will do our best to guarantee that the problems are relevant to a broad range of industries. We will likely call upon many of our colleagues to help create new problems and to perform initial tests of the data sets to be published. We hope that others will follow our lead and provide access to problems in other domains.

We will do our best to provide a variety of both planning and scheduling problems. By doing so we hope to illustrate the need for well integrated planning and scheduling systems that support the entire life-cycle of product design, process design, manufacturing, and distribution. There is no expectation that all participants will attempt to solve all of the published problems. Instead, it is likely that each participant will focus in the area of their greatest expertise and interest.

This is clearly an experiment. We have no way to predict what kind of participation will result from the publication of these problems nor to predict any downstream effects on the course of research and development. We will make every attempt to be responsive to comments and suggestions submitted by participants and we will change the content and format if necessary. Continuation and expansion are entirely dependent upon the interest shown by participants and the time required to maintain this home page, data sets, and submitted results. To the best of our ability, we will keep this forum open until December 31, 1995.

Good Luck!
Barry R. Fox
Mark Ringer



Objectives

The number one purpose for publication of these problems is to accelerate the development and deployment of planning and scheduling technology that will have a significant impact in industry. In order to achieve this purpose, we have sought to satisfy the following objectives:

  1. The problems must be relevant to industry. The emphasis will be on the ability to produce good solutions to realistic problems rather than on the ability to produce optimal solutions to abstract problems.
  2. The problems must be realistic. They should be based upon or derived from real industrial planning and scheduling problems. They should not be made either easier or harder to accommodate the capabilities or goals of the research community.
  3. The problems must advance the state of the practice. They should contain some features or attributes that challenge mainstream commercial products.
  4. The problems must advance the state of the art. They should contain some features or attributes that challenge mainstream research results.
  5. The problems must be public. They must be freely distributable and easily accessible over the Internet.
  6. The problems must be open to all who wish to participate. Professors, graduate students, government and industrial laboratories, and commercial solution providers are all encouraged to participate.
  7. The cost of entry should be low. The data should be easy to read and interpret. Participants should not need to invest a significant amount of effort in developing code to import and export problem data.
  8. Practitioners at all levels of ability should be able to participate. The problems should be delivered in a graduated series so that participants can begin with simple cases and incrementally work their way to more challenging instances.
  9. There should be some reward for participation. The solutions submitted by participants should be quickly and openly published so that all participants can easily compare their performance to others and can easily advertise their accomplishments.
  10. There should be some mechanism for participants to publish comments on the problems sets, papers describing their own research, summaries of their products and services, and even problem sets of their own design.



What's New

March 6, 1995
Planning & Scheduling Benchmarks Homepage posted at
"ftp://ftp.neosoft.com/pub/users/b/benchmrx/homepage.html"
March 8, 1995
Simple solutions to the first 4 problems of Resource Constrained Project Scheduling are provided by Mark Ringer.
March 14, 1995
Final revisions applied. Planning & Scheduling Benchmarks publicly announced.
March 28, 1995
No results have been submitted yet, but in addition to Browser and FTP access we have mailed data sets to 16 different individuals with addresses that circle the globe. We are told by some of our colleagues that these problems are being used in a variety of graduate level courses and seminars on scheduling. Don't forget to write home!
April 15, 1995
The neosoft web server has been upgraded from ftp to http. Please note the new web address: "http://www.neosoft.com/~benchmrx" Some of the documentation and the web page has been revised slightly to facilitate future maintenance. A typographical error was corrected for Mark Ringer's solution to RCPS Problem 1.
April 20, 1995
One official result has been received and validated(see below). Several organizations are actively working on the problems and several of their solutions have been submitted for validation. Don't forget to make an official submission for posting on the Planning & Scheduling Benchmarks homepage.
June 15, 1995
SAS Institute has submitted validated solutions to the first 5 problems. Other organizations have been working on the problems but have not made official submissions to benchmrx@neosoft.com. Be sure to submit your results!
July 13, 1995
A major aerospace corporation has decided to use the benchmark problems as part of their evaluation of suppliers of scheduling software. Although this site was not established for this specific purpose, this is clearly consistent with its objectives and will certainly enable the customer to make a more informed decision. With a few reasonable restricitions, we encourage such use of the benchmarks and would be happy to support similar efforts by other companies.

This page has been accessed 85645 times since June 17th, 1995



Problems

Resource Constrained Project Scheduling

This data set, and its associated series of problems, is based upon large scale assembly but is applicable to a wide variety of problems in engineering, construction, and manufacturing that can generally be described as resource constrained project scheduling. This same data set and series of problems could have originated from a commercial construction project, a petro-chemical plant start-up, an automotive assembly line set-up, Space Shuttle reprocessing, or the assembly of heavy machine tools. We have prepared a first series of problems based upon this data set. Time permitting, we will prepare additional problems that are based upon this same data set or prepare additional data sets that can be the subject of this same series of problems. An overview of the problem set is provided in an online html document. The complete problem set is provided in ascii, postscript, and Microsoft Word format.

In order to give participants a reference point, Mark Ringer has solved the first 4 problems of Resource Constrained Project Scheduling using a simple first fit, feasible interval based algorithm with *no* optimization. The results are summarized below and the actual solutions are provided as data files that can be downloaded.


Documents, Data, and Programs


Reference Solutions


Results



Problems In Preparation

Structural Assembly Planning

Facility Scheduling



Links to other Planning & Scheduling Sources