Approximation algorithms for the min-max regret identical parallel machine scheduling problem with outsourcing and uncertain processing time

Shijin Wang and Wenli Cui

International Journal of Production Research, 2021, vol. 59, issue 15, 4579-4592

Abstract: We consider the robust (min-max regret) version of identical parallel machine scheduling problem, in which jobs may be outsourced to balance total cost against production efficiency. The total cost is measured in terms of the total completion time of jobs processed in-house and the cost of outsourcing the rest. Processing times of in-house jobs are uncertain and they are described as two types of scenarios: discrete and interval. The objective is to obtain a robust (min-max regret) decision that minimises the absolute deviation of total cost from the optimal solution under the worst-case scenario. We first prove the worst-case scenario for any feasible solution. For the interval scenario, we further prove that the maximum regret value can be obtained in polynomial time for any feasible schedule. We also prove that for any discrete scenario, the minimum total cost can be obtained in polynomial time. Since the problem with the interval scenario is strongly NP-hard, we then transform the problem into an equivalent robust single machine scheduling problem. Finally, we develop 2-approximation algorithms for the problem with discrete and interval scenarios, respectively. These results are helpful for bridging the scheduling theory and practice in identical parallel machining environments with outsourcing and uncertain processing times.

Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2020.1766721 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:59:y:2021:i:15:p:4579-4592

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2020.1766721

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().