تقرير
New Bounds for Time-Dependent Scheduling with Uniform Deterioration
| العنوان: | New Bounds for Time-Dependent Scheduling with Uniform Deterioration |
|---|---|
| المؤلفون: | Gkikas, Angelos, Letsios, Dimitrios, Radzik, Tomasz, Steinhöfel, Kathleen |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control |
| الوصف: | Time-dependent scheduling with linear deterioration involves determining when to execute jobs whose processing times degrade as their beginning is delayed. Each job i is associated with a release time r_i and a processing time function p_i(s_i)=alpha_i + beta_i*s_i, where alpha_i, beta_i>0$ are constants and s_i is the job's start time. In this setting, the approximability of both single-machine minimum makespan and total completion time problems remains open. Here, we take a step forward by developing new bounds and approximation results for the interesting special case of the problems with uniform deterioration, i.e.\ beta_i=beta, for each i. The key contribution is a O(1+1/beta)-approximation algorithm for the makespan problem and a O(1+1/beta^2)-approximation algorithm for the total completion time problem. Further, we propose greedy constant-factor approximation algorithms for instances with beta=O(1/n) and beta=Omega(n), where n is the number of jobs. Our analysis is based on a new approach for comparing computed and optimal schedules via bounding pseudomatchings. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2307.00627 |
| رقم الأكسشن: | edsarx.2307.00627 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |