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!
|
| _version_ | 1850036421668110336 |
|---|---|
| author | Jeeraporn Werapun Witchaya Towongpaichayont Anantaporn Hanskunatai |
| author_facet | Jeeraporn Werapun Witchaya Towongpaichayont Anantaporn Hanskunatai |
| author_sort | Jeeraporn Werapun |
| collection | DOAJ |
| description | 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). |
| format | Article |
| id | doaj-art-05356cdcee374ce8ab95fbf7f9fbc057 |
| institution | DOAJ |
| issn | 2667-3053 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Intelligent Systems with Applications |
| spelling | doaj-art-05356cdcee374ce8ab95fbf7f9fbc0572025-08-20T02:57:08ZengElsevierIntelligent Systems with Applications2667-30532025-06-012620050210.1016/j.iswa.2025.200502Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictorJeeraporn Werapun0Witchaya Towongpaichayont1Anantaporn Hanskunatai2Corresponding author.; Computer Science, School of Science, King Mongkut's Institute of Technology, Ladkrabang (KMITL), Bangkok 10520, ThailandComputer Science, School of Science, King Mongkut's Institute of Technology, Ladkrabang (KMITL), Bangkok 10520, ThailandComputer Science, School of Science, King Mongkut's Institute of Technology, Ladkrabang (KMITL), Bangkok 10520, ThailandThe 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).http://www.sciencedirect.com/science/article/pii/S2667305325000286Adaptive unbiased (AU) filteringBranch-and-bound (BnB) algorithm with predictorDeep reduction and intensive processingIndirect assignment with unbiased predictor (UP)Minimum cost of job assignment (Min-JA) |
| spellingShingle | Jeeraporn Werapun Witchaya Towongpaichayont Anantaporn Hanskunatai Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor Intelligent Systems with Applications Adaptive unbiased (AU) filtering Branch-and-bound (BnB) algorithm with predictor Deep reduction and intensive processing Indirect assignment with unbiased predictor (UP) Minimum cost of job assignment (Min-JA) |
| title | Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor |
| title_full | Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor |
| title_fullStr | Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor |
| title_full_unstemmed | Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor |
| title_short | Minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch-and-bound algorithm with the best predictor |
| title_sort | minimum cost of job assignment in polynomial time by adaptive unbiased filtering and branch and bound algorithm with the best predictor |
| topic | Adaptive unbiased (AU) filtering Branch-and-bound (BnB) algorithm with predictor Deep reduction and intensive processing Indirect assignment with unbiased predictor (UP) Minimum cost of job assignment (Min-JA) |
| url | http://www.sciencedirect.com/science/article/pii/S2667305325000286 |
| work_keys_str_mv | AT jeerapornwerapun minimumcostofjobassignmentinpolynomialtimebyadaptiveunbiasedfilteringandbranchandboundalgorithmwiththebestpredictor AT witchayatowongpaichayont minimumcostofjobassignmentinpolynomialtimebyadaptiveunbiasedfilteringandbranchandboundalgorithmwiththebestpredictor AT anantapornhanskunatai minimumcostofjobassignmentinpolynomialtimebyadaptiveunbiasedfilteringandbranchandboundalgorithmwiththebestpredictor |