Title:
Scheduling Benefit-generating Jobs to Capacitated Machines with a Consideration of Fairness
Scheduling Benefit-generating Jobs to Capacitated Machines with a Consideration of Fairness
Time:
*請注意：本週演講時間調整至週日 (US) / 週一 (TW)
02/16 (Sat.) 5 pm PST, 6 pm MST, 7 pm CST, 8 pm EST
02/17 (Sun.) 9 am Taiwan
*演講時間調整回週六 (US) / 週日 (TW)
02/16 (Sat.) 5 pm PST, 6 pm MST, 7 pm CST, 8 pm EST
02/17 (Sun.) 9 am Taiwan
Keywords:
Information Management, Operations Research, Scheduling, Approximation Algorithm, Benefit-workload Relationship, Capacitated Machine, Fairness
Information Management, Operations Research, Scheduling, Approximation Algorithm, Benefit-workload Relationship, Capacitated Machine, Fairness
Abstract:
We consider a problem of allocating jobs to identical machines. Each job has an amount of workload and a benefit collected upon completion. All machines have the same capacity. Under the constraints that jobs cannot be split and that machines have limited capacity, the objective is to maximize the benefit earned by the machine with the least benefit. Our problem is thus a capacitated job allocation problem with consideration of fairness. After showing that this problem is NP-hard, we propose an approximation algorithm modified from the longest processing time (LPT) rule. The algorithm is proved to have a worst-case performance guarantee 1/2 when job benefits are linear to workloads. Different approximation factors are also derived for convex and concave relationships. Finally, numerical studies illustrate the average performances of the algorithm and demonstrates that this algorithm works well when the jobs exhibit economy of scale but not so well when they exhibit diminishing marginal benefits.
We consider a problem of allocating jobs to identical machines. Each job has an amount of workload and a benefit collected upon completion. All machines have the same capacity. Under the constraints that jobs cannot be split and that machines have limited capacity, the objective is to maximize the benefit earned by the machine with the least benefit. Our problem is thus a capacitated job allocation problem with consideration of fairness. After showing that this problem is NP-hard, we propose an approximation algorithm modified from the longest processing time (LPT) rule. The algorithm is proved to have a worst-case performance guarantee 1/2 when job benefits are linear to workloads. Different approximation factors are also derived for convex and concave relationships. Finally, numerical studies illustrate the average performances of the algorithm and demonstrates that this algorithm works well when the jobs exhibit economy of scale but not so well when they exhibit diminishing marginal benefits.
No comments:
Post a Comment