Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor
The minimum cost of job assignment (Min-JA) is one of the practical NP-hard problems to manage the optimization in science-and-engineering applications. Formally, the optimal solution of the Min-JA can be computed by the branch-and-bound (BnB) algorithm (with the efficient predictor) in O(n!), n = p...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-06-01
|
| Series: | Intelligent Systems with Applications |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2667305325000286 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The minimum cost of job assignment (Min-JA) is one of the practical NP-hard problems to manage the optimization in science-and-engineering applications. Formally, the optimal solution of the Min-JA can be computed by the branch-and-bound (BnB) algorithm (with the efficient predictor) in O(n!), n = problem size, and O(n3) in the best case but that best case hardly occurs. Currently, metaheuristic algorithms, such as genetic algorithms (GA) and swarm-optimization algorithms, are extensively studied, for polynomial-time solutions. Recently, unbiased filtering (in search-space reduction) could solve some NP-hard problems, such as 0/1-knapsack and multiple 0/1-knapsacks with Latin square (LS) of m-capacity ranking, for the ideal solutions in polynomial time. To solve the Min-JA problem, we propose the adaptive unbiased-filtering (AU-filtering) in O(n3) with a new hybrid (search-space) reduction (of the indirect metaheuristic strategy and the exact BnB). Innovation-and-contribution of our AU-filtering is achieved through three main steps: 1. find 9 + n effective job-orders for the good initial solutions (by the indirect assignment with UP: unbiased predictor), 2. improve top 9-solutions by the indirect improvement of the significant job-orders (by Latin square of n permutations plus n complex mod-functions), and 3. classify objects (from three of the best solutions) for AU-filtering (on large n) with deep-reduction (on smaller n’) and repeat (1)-(3) until n’ < 6, the exact BnB is applied. In experiments, the proposed AU-filtering was evaluated by a simulation study, where its ideal results outperformed the best results of the hybrid swarm-GA algorithm on a variety of 2D datasets (n ≤ 1000). |
|---|---|
| ISSN: | 2667-3053 |