1186. The Unreliable Job Selection and Sequencing Problem
Invited abstract in session MB-12: Scheduling models and algorithms, stream Scheduling and Project Management.
Monday, 10:30-12:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Emmeline Perneel
|
| ORSTAT, KU Leuven | |
| 2. | Alessandro Agnetis
|
| Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena | |
| 3. | Roel Leus
|
| ORSTAT, KU Leuven | |
| 4. | Ilaria Salvadori
|
| Department of Information Engineering and Mathematics, University of Siena |
Abstract
We introduce the Unreliable Job Selection and Sequencing Problem (UJSSP), in which a subset of a set of jobs is selected for processing on a single machine that is subject to failure. Each job incurs a cost if selected and yields a reward upon successful completion. A job is completed successfully only if the machine does not fail before or during its execution, with failure probabilities varying across jobs. The objective is to determine an optimal subset and sequence of jobs to maximize the expected net profit. We establish the computational complexity of UJSSP, proving its NP-hardness when job costs are not identical. Additionally, we present a compact MILP formulation and derive an efficiently computable upper bound for the optimal solution. To tackle large problem instances, we develop a novel exact solution method and evaluate its performance through extensive computational experiments.
Keywords
- Algorithms
- Combinatorial Optimization
- Scheduling
Status: accepted
Back to the list of papers