A Neural Network Approach to Job-Shop Scheduling

D. N. Zhou, V. Cherkassky, T. R. Baldwin, D. E. Olson

Research output: Contribution to journalArticle

65 Scopus citations

Abstract

This paper presents a novel analog computational network for solving NP-complete constraint satisfaction problems, i.e., job-shop scheduling. In contrast to most neural approaches to combinatorial optimization based on quadratic energy cost function, we propose to use linear cost functions. As a result, the network complexity (number of interconnections) grows only linearly with problem size, and large-scale implementations become possible. The proposed approach is related to the linear programming network described by Tank and Hopfield. which also uses a linear cost function for a simple optimization problem. In this paper we show how to map a difficult constraint satisfaction problem (job-shop scheduling) onto a simple neural net, where the number of neural processors equals the number of subjobs (operations), and the number of interconnections grows linearly with the total number of operations. Simulations show that our approach produces better solutions than existing neural approaches to job-shop scheduling, i.e. the TSP-type Hopfield approach and integer linear programming approach of Foo and Takefuji in terms of the quality of the solution and the network complexity, i.e., the number of neurons and the number of resistive interconnections.

Original languageEnglish (US)
Pages (from-to)175-179
Number of pages5
JournalIEEE Transactions on Neural Networks
Volume2
Issue number1
DOIs
StatePublished - Jan 1991

Fingerprint Dive into the research topics of 'A Neural Network Approach to Job-Shop Scheduling'. Together they form a unique fingerprint.

  • Cite this