b******e
发帖数: 432 | 1 Morning Coffee. Every morning, customers 1..n show up to get their morning
espresso-based concoction from Cafe Zoo. Suppose the omniscient barista
actually knows all of the customers, and knows their orders, o_1..o_n. Some
customers are nicer people; let T_i be the baristas expected tip from
customer i. Some drinks like a simple double-shot, are easy and fast, while
some other orders, like a hazelnut mocha soy-milk latte take longer. Let t_i
be the time it takes to make drink o_i . Assume the ba | l******e
发帖数: 470 | 2 very hard problem
google this paper
Approximation Schemes for Minimizing Average Weighted Completion Time
with Release Dates
I dont think the objective function you proposed is a good one in this
application though.
Some
while
_i
done
algorithm
【在 b******e 的大作中提到】
: Morning Coffee. Every morning, customers 1..n show up to get their morning
: espresso-based concoction from Cafe Zoo. Suppose the omniscient barista
: actually knows all of the customers, and knows their orders, o_1..o_n. Some
: customers are nicer people; let T_i be the baristas expected tip from
: customer i. Some drinks like a simple double-shot, are easy and fast, while
: some other orders, like a hazelnut mocha soy-milk latte take longer. Let t_i
: be the time it takes to make drink o_i . Assume the ba
| a****9
发帖数: 418 | 3 greedy
pick T_i/t_i in decreasing order
Some
while
_i
done
algorithm
【在 b******e 的大作中提到】
: Morning Coffee. Every morning, customers 1..n show up to get their morning
: espresso-based concoction from Cafe Zoo. Suppose the omniscient barista
: actually knows all of the customers, and knows their orders, o_1..o_n. Some
: customers are nicer people; let T_i be the baristas expected tip from
: customer i. Some drinks like a simple double-shot, are easy and fast, while
: some other orders, like a hazelnut mocha soy-milk latte take longer. Let t_i
: be the time it takes to make drink o_i . Assume the ba
| a****9
发帖数: 418 | 4 这里是单机offline调度,
问题不一样的
【在 l******e 的大作中提到】
: very hard problem
: google this paper
: Approximation Schemes for Minimizing Average Weighted Completion Time
: with Release Dates
: I dont think the objective function you proposed is a good one in this
: application though.
:
: Some
: while
: _i
| l******e
发帖数: 470 | 5 you might want to say T_i/t_i ?
I think the Smith ratio only gives optimal solution when all jobs are
release atthe same time. I thought we were required to consider different
release times since lz mentioned the arrival order explicitly..
The paper i mentioned also solved the single machine case.
【在 a****9 的大作中提到】
: greedy
: pick T_i/t_i in decreasing order
:
: Some
: while
: _i
: done
: algorithm
| b******e
发帖数: 432 | 6 非常感谢楼上的建议s。
"Assume the barista can make the drinks in any order that she wishes"我认为
这句话实际上说明"all jobs are release at the same time"
So, greedy might be OK.
另外再问一道：
Friends. Reword the following statement as a theorem about undirected
graphs, and then prove it. Assume that friendship is symmetric but not re
exive.
(a) Any group of at least two people contains at least two people with the
same number of friends in the group. | a**********s
发帖数: 588 | 7 鸽洞原理, 分有没有人没有朋友的两种情况讨论, 详细解答已经发给你了
【在 b******e 的大作中提到】
: 非常感谢楼上的建议s。
: "Assume the barista can make the drinks in any order that she wishes"我认为
: 这句话实际上说明"all jobs are release at the same time"
: So, greedy might be OK.
: 另外再问一道：
: Friends. Reword the following statement as a theorem about undirected
: graphs, and then prove it. Assume that friendship is symmetric but not re
: exive.
: (a) Any group of at least two people contains at least two people with the
: same number of friends in the group.
| b******e
发帖数: 432 | |
|
