Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria

Yunqiang Yin, Youhua Chen, Kaida Qin and Dujuan Wang ()
Additional contact information
Yunqiang Yin: University of Electronic Science and Technology of China
Youhua Chen: Department of Management Sciences, City University of Hong Kong
Kaida Qin: Kunming University of Science and Technology
Dujuan Wang: Business School, Sichuan University

Journal of Scheduling, 2019, vol. 22, issue 3, No 5, 315-333

Abstract: Abstract This paper considers a two-agent scheduling problem in which each agent has a set of jobs that competes with that of another agent for the use of m unrelated parallel machines. Each agent aims to minimize a certain scheduling criterion related to the completion times of its jobs. The overall objective is to minimize the total completion time of the jobs of one agent while keeping the weighted number of tardy jobs of another agent within a given limit. We introduce a novel column generation scheme, called in-out column generation, to maintain the stability of dual variables and then embed this scheme into a branch-and-price framework. A greedy heuristic is used to obtain a set of initial columns to start the in-out column generation. The pricing subproblem in the column generation scheme is formulated as a single-machine scheduling problem that can be solved using dynamic programming techniques. An efficient branching strategy that is compatible with pricing subproblems is also proposed. The extensive computational results that are obtained by using randomly generated data demonstrate that our branch-and-price algorithm is singularly efficient and promising.

Keywords: Scheduling; Two agents; Column generation; Dynamic programming algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0583-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:jsched:v:22:y:2019:i:3:d:10.1007_s10951-018-0583-z

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

DOI: 10.1007/s10951-018-0583-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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