A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
type: Item
instance of: scholarly article
title: A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
zbMATH Open document ID: 1426.90131
DOI: 10.1155/2017/5791796
author: Myoung-Ju Park
author: Byung-Cheon Choi
published in: Mathematical Problems in Engineering
publication date: 2018-11-05T00:00:00Z
review text: Summary: We consider a single-machine scheduling problem with an outsourcing option in an environment where the processing time and outsourcing cost are uncertain. The performance measure is the total cost of processing some jobs in-house and outsourcing the rest. The cost of processing in-house jobs is measured as the total weighted completion time, which can be considered the operating cost. The uncertainty is described through either an interval or a discrete scenario. The objective is to minimize the maximum deviation from the optimal cost of each scenario. Since the deterministic version is known to be NP-hard, we focus on two special cases, one in which all jobs have identical weights and the other in which all jobs have identical processing times. We analyze the computational complexity of each case and present the conditions that make them polynomially solvable.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 6972247
Wikidata QID: Q59147634
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2017/5791796
OpenAlex ID: W2594037866
cites work: Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
cites work: Robust discrete optimization and its applications
cites work: Min-max and min-max regret versions of combinatorial optimization problems: A survey
cites work: Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
cites work: A survey on offline scheduling with rejection
cites work: Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
cites work: Techniques for scheduling with rejection
cites work: Job selection in a heavily loaded shop
cites work: A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
cites work: On a constant factor approximation for minmax regret problems using a symmetry point scenario
cites work: A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion
cites work: Complexity of minimizing the total flow time with interval data and minmax regret criterion
cites work: Q4198056
cites work: An approximation algorithm for interval data minmax regret combinatorial optimization problems
Recommended article: Complexity of single machine scheduling problems under scenario-based uncertainty
Recommended article: Minimizing maximum cost for a single machine under uncertainty of processing times
Recommended article: A single-machine scheduling problem with random processing times
Recommended article: Single machine scheduling problems with uncertain parameters and the OWA criterion
Recommended article: Single machine scheduling to minimize the number of late jobs under uncertainty.
Recommended article: Single machine robust scheduling with budgeted uncertainty
Recommended article: Single machine scheduling under market uncertainty
Recommended article: Q3307656
Recommended article: Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
Recommended article: The stochastic single machine scheduling problem with earliness and tardiness costs
description: scientific article; zbMATH DE number 6972247