Some two-agent single-machine scheduling problems to minimize minmax and minsum of completion times

Xiaoling Cao, Wen-Hsing Wu, Wen-Hung Wu and Chin-Chia Wu ()
Additional contact information
Xiaoling Cao: Yangtze University
Wen-Hsing Wu: Yuanpei University
Wen-Hung Wu: Kang-Ning University
Chin-Chia Wu: Feng Chia University

Operational Research, 2018, vol. 18, issue 2, No 2, 293-314

Abstract: Abstract In this study we address several two-agent problems in which the measure criterion is to minimize the maximum cost or total weighted completion of all the jobs, while subject to an upper bound on the maximum cost of agent A. In term of minimizing the maximum cost of all the jobs subject to an upper bound on the maximum cost of agent A, we discuss some optimal properties and propose polynomial time solution algorithm to solve it. In term of minimizing the total weighted completion of all the jobs subject to an upper bound on the maximum cost of agent A, we analyze the complexity, show that this problem is NP-hard, and discuss it under special cases. In addition, for minimizing the total weighted completion of all the jobs subject to an upper bound on the makespan of agent A, we derive some dominance rules to be used in a branch-and-bound method and propose a heuristic for finding the optimal and near-optimal solution, respectively. A computational simulation is also provided to determine the performance of the proposed algorithms.

Keywords: Scheduling; Two-agent; Maximum cost; Total weighted complete time (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-016-0265-6 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:operea:v:18:y:2018:i:2:d:10.1007_s12351-016-0265-6

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-016-0265-6

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

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