Journal
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE
Volume 104, Issue -, Pages -Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.engappai.2021.104368
Keywords
Job shop scheduling; Infeasibility; Repairs; Evolutionary algorithms; Solution builders
Categories
Funding
- Spanish Government [TIN2016-79190-R, PID2019106263RBI00]
- Principality of Asturias, Spain [IDI/2018/000176]
Ask authors/readers for more resources
We address the task of repairing infeasibility in job shop scheduling problems with a hard constraint on the maximum makespan. By adopting a job-based view of repairs and proposing enhancements to a genetic algorithm, we aim to improve efficiency and effectiveness in solving the problem. The proposed methods show significant improvements in experimental results.
We address the task of repairing infeasibility in the context of infeasible job shop scheduling problems with a hard constraint on the maximum makespan allowed. For this purpose, we adopt a job-based view of repairs, that allows for dropping some of the jobs and so gives rise to the problem of computing the largest subset of jobs that can be scheduled under the makespan constraint. Recent work proposed a genetic algorithm for solving this problem, which integrates an efficient solution builder for defining the search space. In this paper, we build on this earlier work and make several contributions. We provide a formal analysis of both the search space and the solution builder. Then, we propose two important enhancements to the genetic algorithm: first, we develop a new solution builder aimed at reducing the number of feasibility tests, making the search process more efficient. In addition, we propose a more effective procedure for testing the feasibility of different subsets of jobs under the given makespan constraint based on the use of a light-weight genetic algorithm. Experimental results show that the proposed methods are effective at solving the problem, and that the enhancements bring significant improvements.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available