Optimal scheduling on unrelated parallel machines with combinatorial auction.
Saved in:
| Title: | Optimal scheduling on unrelated parallel machines with combinatorial auction. |
|---|---|
| Authors: | Yan, Xue1 (AUTHOR) xueyan9103@163.com, Wang, Ting2,3 (AUTHOR) tingwang@nufe.edu.cn, Shi, Xuefei4 (AUTHOR) sxf0429@126.com |
| Source: | Annals of Operations Research. Jan2025, Vol. 344 Issue 2, p937-963. 27p. |
| Subjects: | Computer scheduling, Computer software, Scheduling software, Computer science, Dynamic programming |
| Abstract: | Outsourcing operations have become an essential factor in enhancing the competitive advantage of software development enterprises. In this work, we examine the application of combinatorial auction in technician assignment and outsourcing service procurement, which is conducted by software enterprises to minimize the total cost of developing all the software. It gives rise to an unrelated parallel machine scheduling problem incorporating combinatorial auction (UPMSCA). Here, the jobs represent the software to be developed, and they consume the perishable time resources of the development technicians, which can be translated into monetary costs. The objective is to schedule the jobs on parallel machines or select the bid with the lowest cost. To solve the problem, we propose an arc-flow model and a set-partitioning formulation with column-based constraints. A branch-and-price algorithm with four branching rules is proposed and utilizes an effective dynamic programming algorithm to solve the pricing subproblem in the pattern-based formulation. To speed up computation, a bidirectional search method and a dominance rule are applied. Results from extensive computational tests on 100 sets of randomly generated instances demonstrate the performance of our algorithm. [ABSTRACT FROM AUTHOR] |
| Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | Outsourcing operations have become an essential factor in enhancing the competitive advantage of software development enterprises. In this work, we examine the application of combinatorial auction in technician assignment and outsourcing service procurement, which is conducted by software enterprises to minimize the total cost of developing all the software. It gives rise to an unrelated parallel machine scheduling problem incorporating combinatorial auction (UPMSCA). Here, the jobs represent the software to be developed, and they consume the perishable time resources of the development technicians, which can be translated into monetary costs. The objective is to schedule the jobs on parallel machines or select the bid with the lowest cost. To solve the problem, we propose an arc-flow model and a set-partitioning formulation with column-based constraints. A branch-and-price algorithm with four branching rules is proposed and utilizes an effective dynamic programming algorithm to solve the pricing subproblem in the pattern-based formulation. To speed up computation, a bidirectional search method and a dominance rule are applied. Results from extensive computational tests on 100 sets of randomly generated instances demonstrate the performance of our algorithm. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 02545330 |
| DOI: | 10.1007/s10479-024-06283-z |
