View in EDS HTML Full Text PDF Full Text

Optimal scheduling on unrelated parallel machines with combinatorial auction.

Saved in:
Bibliographic Details
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.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 182278107
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Optimal scheduling on unrelated parallel machines with combinatorial auction.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Yan%2C+Xue%22">Yan, Xue</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> xueyan9103@163.com</i><br /><searchLink fieldCode="AR" term="%22Wang%2C+Ting%22">Wang, Ting</searchLink><relatesTo>2,3</relatesTo> (AUTHOR)<i> tingwang@nufe.edu.cn</i><br /><searchLink fieldCode="AR" term="%22Shi%2C+Xuefei%22">Shi, Xuefei</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> sxf0429@126.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Annals+of+Operations+Research%22">Annals of Operations Research</searchLink>. Jan2025, Vol. 344 Issue 2, p937-963. 27p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computer+scheduling%22">Computer scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Scheduling+software%22">Scheduling software</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+science%22">Computer science</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=182278107
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s10479-024-06283-z
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 27
        StartPage: 937
    Subjects:
      – SubjectFull: Computer scheduling
        Type: general
      – SubjectFull: Computer software
        Type: general
      – SubjectFull: Scheduling software
        Type: general
      – SubjectFull: Computer science
        Type: general
      – SubjectFull: Dynamic programming
        Type: general
    Titles:
      – TitleFull: Optimal scheduling on unrelated parallel machines with combinatorial auction.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Yan, Xue
      – PersonEntity:
          Name:
            NameFull: Wang, Ting
      – PersonEntity:
          Name:
            NameFull: Shi, Xuefei
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 01
              Text: Jan2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 02545330
          Numbering:
            – Type: volume
              Value: 344
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Annals of Operations Research
              Type: main
ResultId 1