A neural network approach to job-shop scheduling

Area of Science:

• Computational neuroscience
• Operations research
• Artificial intelligence

Background:

• Job-shop scheduling is an NP-complete constraint satisfaction problem.
• Existing neural network approaches often use quadratic cost functions, limiting scalability.
• Linear programming networks offer a simpler cost function but have limitations.

Purpose of the Study:

• To present a novel analog computational network for solving NP-complete constraint satisfaction problems, specifically job-shop scheduling.
• To propose the use of linear cost functions to overcome the scalability limitations of quadratic cost functions in neural optimization.
• To demonstrate that the proposed network achieves better solution quality and lower complexity compared to existing methods.

Main Methods:

• Developed a novel analog computational network utilizing linear cost functions.
• Mapped job-shop scheduling problems onto a neural network where processors equal subjobs and interconnections grow linearly.
• Compared the network's performance against the traveling salesman problem-type Hopfield approach and an integer linear programming approach.

Main Results:

• The network complexity (neurons and interconnections) scales linearly with problem size, enabling large-scale implementations.
• The proposed approach demonstrated superior solution quality compared to existing neural and integer linear programming methods.
• Achieved a significant reduction in network complexity for job-shop scheduling problems.

Conclusions:

• The novel analog network with linear cost functions provides an effective and scalable solution for job-shop scheduling.
• This approach represents a significant advancement over traditional neural and integer programming methods for complex optimization tasks.
• The linear scaling of network complexity makes it suitable for tackling large, real-world scheduling challenges.