Optimal scheduling on unrelated parallel machines with combinatorial auction

Xue Yan (), Ting Wang () and Xuefei Shi ()
Additional contact information
Xue Yan: Nanjing Audit University
Ting Wang: Nanjing University of Finance and Economics
Xuefei Shi: Jiangxi University of Science and Technology

Annals of Operations Research, 2025, vol. 344, issue 2, No 14, 937-963

Abstract: 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.

Keywords: Software outsourcing; Unrelated parallel machines; Scheduling; Branch-and-price; Combinatorial auction (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06283-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:344:y:2025:i:2:d:10.1007_s10479-024-06283-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-06283-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().