M*******a
发帖数: 1633 | 1 A service system has n DIFFERENT servers; each one provides one unique
service to the clients. Clients submit requests to the service system, each
request may have multiple sub-requests; each sub-request is to a DIFFERENT
server. A request can have at most n sub-requests. Each sub-request takes 1
time unit to finish at any server. The finish time of a request is the
finish time of its LAST finished sub-request. The notation "total request
finish time" is the sum of all requests' finish time.
1. Design an off-line algorithm to reorder the execution order of sub-
requests on the servers, so that "total request finish time" can be
minimized (if multiple solutions exist, only one solution is enough).
Discuss the complexity of the algorithm.
2. Discuss feasible algorithms that can achieve sub-optimal solutions with N
~ 10000.
3. Suppose the sub-requests can be queued at each server, and the servers
are running all the time. Discuss feasible on-line algorithms that can
achieve sub-optimal solutions with N ~ 10000. |
r****s
发帖数: 1025 | 2 这题有意思，什么叫online,什么叫offline？
each
1
【在 M*******a 的大作中提到】
: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).
|
c*******y
发帖数: 98 | 3 第一问类似于给定workload然后装箱（n个）问题。这个是不是纯静态优化的问题？应
当有最优解，不过没学过不知道咋做。
第二问是dynamic workload scheduling/balancing，估计最后是想让average
response delay比较短？因为不能预知接下来的input，所以optimal就不大可能。这个
换我那就只能xb说了，等大牛解释。
楼主是面的
each
1
【在 M*******a 的大作中提到】
: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).
|
l******6
发帖数: 340 | 4 If all subrequests of a request are flat and requests are independent
offline algorithm:
sort requests by number of subrequest than greedy assign subrequests to most
idle server
onlie algorithm:
greedy assign subrequests to most idle server |
r****s
发帖数: 1025 | 5 每个server都不一样，没法greedy吧
"each one provides one unique
service to the clients" |
F********m
发帖数: 530 | |
f*****e
发帖数: 2992 | 7 不能证明approximation ratio的都不是好题。
each
1
【在 M*******a 的大作中提到】
: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).
|
o***g
发帖数: 2784 | 8 sub-request之间的关系是怎样的？是可以同时进行的？还是必须顺序进行？
如果可以同时进行，那就简单了。如果必须顺序做，那就复杂了。
each
1
【在 M*******a 的大作中提到】
: A service system has n DIFFERENT servers; each one provides one unique
: service to the clients. Clients submit requests to the service system, each
: request may have multiple sub-requests; each sub-request is to a DIFFERENT
: server. A request can have at most n sub-requests. Each sub-request takes 1
: time unit to finish at any server. The finish time of a request is the
: finish time of its LAST finished sub-request. The notation "total request
: finish time" is the sum of all requests' finish time.
: 1. Design an off-line algorithm to reorder the execution order of sub-
: requests on the servers, so that "total request finish time" can be
: minimized (if multiple solutions exist, only one solution is enough).
|
M*******a
发帖数: 1633 | 9 可以同时进行也可以不同时进行
Depend on the availability of servers
【在 o***g 的大作中提到】
: sub-request之间的关系是怎样的？是可以同时进行的？还是必须顺序进行？
: 如果可以同时进行，那就简单了。如果必须顺序做，那就复杂了。
:
: each
: 1
|
o***g
发帖数: 2784 | 10 你的意思是所有sub request之间都没有约束关系，那就简单了。并且所有sub request
都是运行1 unit时间。
那就是所有request都变成sub request，然后找哪个server上排了最多sub request，
这个就是最长时间了
【在 M*******a 的大作中提到】
: 可以同时进行也可以不同时进行
: Depend on the availability of servers
|
M*******a
发帖数: 1633 | 11 The notation "total request finish time" is the sum of all requests' finish
time.
Not
Earliest time that all request can be finished.
request
【在 o***g 的大作中提到】
: 你的意思是所有sub request之间都没有约束关系，那就简单了。并且所有sub request
: 都是运行1 unit时间。
: 那就是所有request都变成sub request，然后找哪个server上排了最多sub request，
: 这个就是最长时间了
|
