تقرير
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 |
الوصف غير متاح. |