Parameterized Multi-Scenario Single-Machine Scheduling Problems
- PDF / 389,776 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 198 Views
(0123456789().,-volV) (0123456789().,-volV)
Parameterized Multi-Scenario Single-Machine Scheduling Problems Danny Hermelin1 • George Manoussakis1 • Michael Pinedo2 Dvir Shabtay1 • Liron Yedidsion1
•
Received: 29 April 2019 / Accepted: 16 March 2020 Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study a class of multi-scenario single-machine scheduling problems. In this class of problems, we are given a set of scenarios with each one having a different realization of job characteristics. We consider these multi-scenario problems where the scheduling criterion can be any one of the following three: The total weighted completion time, the weighted number of tardy jobs, and the weighted number of jobs completed exactly at their due-date. As all the resulting problems are NP-hard, our analysis focuses on whether any one of the problems becomes tractable when some specific natural parameters are of limited size. The analysis includes the following parameters: The number of jobs with scenario-dependent processing times, the number of jobs with scenario-dependent weights, and the number of different due-dates. Keywords Single machine scheduling Multi-scenario scheduling Parameterized complexity Fixed-parameter tractability Robust job schedule
& Dvir Shabtay [email protected] Danny Hermelin [email protected] George Manoussakis [email protected] Michael Pinedo [email protected] Liron Yedidsion [email protected] 1
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, P.O.B. 653, 8410501 Beer-Sheva, Israel
2
Stern School of Business, New York University, 44 West 4th Street, New York, NY 10012, USA
123
Algorithmica
1 Introduction Models for solving real-life scheduling problems are vastly influenced by values of job characteristics such as processing time, weight, etc. The common assumption in deterministic scheduling is that there is only one fixed value for each job characteristic. However, such an assumption may fail to capture many real life applications, where job characteristics may be uncertain at the time when the scheduler has to make his decisions. There are several different approaches to analyze scheduling problems with uncertainty, including (i) the stochastic approach [10, 16, 17, 33, 35] where values are drawn from given probability distributions; (ii) the interval approach [6, 23, 27, 36] where values are restricted to predefined intervals; and the multiscenario approach [2, 7, 7, 14, 15, 22, 28, 37], where there are q different scenarios, and in each scenario the value of each possible job characteristic is certain and known in advance. Given a scheduling criterion, the most common objective in a stochastic approach is to find a job schedule or policy that optimizes (usually minimizes) the expected value of the scheduling criterion at hand. In the two other approaches the common objective is to find a robust job schedule for which the scheduling criterion value will be satisfactory for each possible scenario (in the mult
Data Loading...
