Scheduling parallel processors with resource restricted and setup-cost dependent jobs

Date

1992-05

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Recently, the Resource Constrained Scheduling Problem (RCSP) has become a popular topic in scheduling. The RCSP considers the constraint that activities require more than one unit of resource at a time. This dissertation presents a similar scheduling problem to the RCSP, except that it has a different restriction on the resource constraint. In this research, the resource restriction is that only part of the resources are available to a certain group of activities. Each activity requires exactly one resource. However, because of technological constraints, not every resource is available for every activity. In order to distinguish the difference between this research and the RCSP, the term "resource restricted" is used instead of "resource constrained. " This research considers a single-stage scheduling problem consisting of parallel non-identical processors with sequence-dependent setup costs. The parallel processors have similar characteristics, but they may not be completely identical. That is, some jobs may only be processed on certain kinds of machines. The restrictions on the dependency among jobs and machines prevent solution of the problem by the existing methods. The research problem was investigated and several solution approaches, including one optimization method, two heuristics, and a random sampling technique, were developed. A 2 X 2 X 7 factorial design was used for conducting the experiments. The computational results were collected by using a computer program named RRSS which is written by the author in the C language for implementing the algorithms developed in this research. In addition, the Friedman test, a non-parametric statistical test, was used to analyze the computational results. If the reader is interested in using the RRSS software for academic purposes, he or she may contact the Department of Industrial Engineering, Texas Tech University, Lubbock, Texas, to obtain a copy of the executable code.

Description

Keywords

Production scheduling, Traveling-salesman problem, Parallel processing (Electronic computers)

Citation