Large scheduling problems with bivalent costs

Open Access
Publisher Website
Google Scholar
Abstract
Consider n items to be produced on one facility in a cyclic manner, and assume the costs of resetting the facility (so that an item can follow immediately after the completion of the previous one), to be bivalent (two-valued); i.e., either resetting of the facility is necessary and the cost is W, or no resetting is necessary and the cost is zero. The problem considered in this paper is that of scheduling the n items so as to minimise the total resetting cost incurred. This problem is a special case of the well known travelling salesman problem and could be solved as such, although only small size problems could be treated in this way. The present paper describes an alternative formulation of the problem in graph-theoretic terms, which enables the solution of large size problems (involving several hundreds or thousands of items). Computational results are given for six problems varying in size from 50 to 500 items.

This publication has 0 references indexed in Scilit: