A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
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.
- Complexity of single machine scheduling problems under scenario-based uncertainty
- Minimizing maximum cost for a single machine under uncertainty of processing times
- A single-machine scheduling problem with random processing times
- Single machine scheduling problems with uncertain parameters and the OWA criterion
- Single machine scheduling to minimize the number of late jobs under uncertainty.
- Single machine robust scheduling with budgeted uncertainty
- Single machine scheduling under market uncertainty
- Single-machine just-in-time scheduling with outsourcing
- Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
- The stochastic single machine scheduling problem with earliness and tardiness costs
- A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion
- A 2-approximation for minmax regret problems via a mid-point scenario optimal solution
- A survey on offline scheduling with rejection
- An approximation algorithm for interval data minmax regret combinatorial optimization problems
- Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine
- Complexity of minimizing the total flow time with interval data and minmax regret criterion
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Job selection in a heavily loaded shop
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
- On a constant factor approximation for minmax regret problems using a symmetry point scenario
- Robust discrete optimization and its applications
- Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production
- Techniques for scheduling with rejection
- Single machine scheduling problems with uncertain parameters and the OWA criterion
- Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
- A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs
- A state-of-the-art survey on multi-scenario scheduling
- A hybrid genetic algorithm for scheduling jobs sharing multiple resources under uncertainty
This page was built for publication: A single-machine scheduling problem with uncertainty in processing times and outsourcing costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1992893)
