02/02/2021

Equitable Scheduling on a Single Machine

Klaus Heeger, Dan Hermelin, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Dvir Shabtay

Keywords:

Abstract Paper Similar Papers

Abstract: We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k <= m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38948506
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 12:46 
 0
 0
 0
 0
 14:28 
 0
 0
 0
 0
 22:51 
 0
 0
 0
 0
 13:45 
 0
 0
 0
 0
 21:54 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 16:47 
 0
 0
 0
 0
 15:14 
 0
 0
 0
 0
 25:11 
 0
 0
 0
 0
 20:17 
 0
 0
 0
 0
 15:13 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 19:58 
 0
 0
 0
 0
 5:15 
 0
 0
 0
 0
 14:48 
 0
 0
 0
 0
 14:05 
 0
 0
 0
 0
 19:13 
 0
 0
 0
 0
 3:22 
 0
 0
 0
 0
 7:27 
 0
 0
 0
 0
 15:05 
 0
 0
 0
 0
 27:27 
 1
 1
 0
 0
 3:29 
 0
 0
 0
 0
 12:10 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 15:40 
 0
 0
 0
 0
 4:51 
 1
 1
 0
 0
 14:40 
 0
 0
 0
 0
 14:57 
 0
 0
 0
 0
 11:59 
 0
 0
 0
 0
 17:50 
 0
 0
 0
 0
 7:33 
 0
 0
 0
 0
 15:10 
 0
 0
 0
 0
 12:08 
 0
 0
 0
 0
 3:24 
 0
 0
 0
 0
 25:48 
 0
 0
 0
 0
 23:54 
 0
 0
 0
 0
 13:10 
 0
 0
 0
 0
 12:41 
 0
 0
 0
 0
 17:18