Automated Design of Multipass Heuristics for Resource-Constrained Job Scheduling With Self-Competitive Genetic Programming
Abstract : Resource constraint job scheduling is an important combinatorial optimization problem with many practical applications. This problem aims at determining a schedule for executing jobs on machines satisfying several constraints (e.g., precedence and resource constraints) given a shared central resource while minimizing the tardiness of the jobs. Due to the complexity of the problem, several exact, heuristic, and hybrid methods have been attempted. Despite their success, scalability is still a major issue of the existing methods. In this study, we develop a new genetic programming algorithm for resource constraint job scheduling to overcome or alleviate the scalability issue. The goal of the proposed algorithm is to evolve effective and efficient multipass heuristics by a surrogate-assisted learning mechanism and self-competitive genetic operations. The experiments show that the evolved multipass heuristics are very effective when tested with a large dataset. Moreover, the algorithm scales very well as excellent solutions are found for even the largest problem instances, outperforming existing metaheuristic and hybrid methods.
? These studies mainly examined the performance of simple combinations of different existing dispatching rules (DRs) and due-date assignment rules (DDARs).
? Comparing the evolved scheduling policies with existing scheduling policies from combinations of existing dispatching rules and due-date assignment rules.
? The function set used for DDARs is also applied here along with min, max and abs, which commonly appear in existing CDRs.
? The evolved non-dominated scheduling policies (SPs) are then compared with the existing SPs based on combinations of well-known dispatching rules with dynamic and regression-based due-date assignment rules.
? Priority heuristics are usually the quickest way of obtaining “goodenough” solutions and have been useful for a range of different combinatorial optimization problems.
? It operates on a set of problem attributes and mathematical operators to evolve heuristics.
? While these algorithms have the benefit of producing good solutions, they often lack the generalization, flexibility and intuitiveness needed for real-world problems.
? This tightness makes the problem landscape significantly difficult to navigate for an algorithm and introduces the possibility of being stuck at the local optima.
• A set of instances were used to train the rules and the performance of the rules evolved by the proposed methods are evaluated by a set of test instances.
• Some dynamic DDARs without the need of finding optimal coefficients have also been proposed, such as Dynamic Total Work Content (DTWK), Dynamic Processing Plus Waiting (DPPW) [37], and ADRES.
• The proposed GP method is used to create the priority rule for a single machine in both static and dynamic environments.
• They also proposed an interesting approach to provide some adaptive behaviours for the evolved rules by presenting a GP-3 system that evolves three components, a discriminant function and two dispatching rules.
? A dynamic variant of the classical RCPSP is formulated and a multi-objective GPHH is proposed for discovering priority heuristics, with strong performance and low complexity, to deal with dynamic instances.
? The heuristics discovered in this study exhibit, either, on-par or superior performance in comparison to existing human designed approaches.
? The performance of any given algorithm or solution methodology is affected by a number of factors such as solution representation, schedule generation scheme, instance characteristics, etc.
? Some researchers have tried to combine priority rules with sampling methods as a way to further improve their performance.
? These lower-bounds are commonly used in RCPSP studies to measure the performance of algorithms.
|