Server Upgrade Planning

Problem Statement

Server Upgrade Planning Problem Description Two servers need to be upgraded. The first server needs t1 seconds of upgrade work and the second server needs t2 seconds of upgrade work. Time is divided into seconds numbered 1, 2, 3, ... . In any one second, at most one server can be upgraded, and that server completes one second of its upgrade work. A server's upgrade work does not have to be done in consecutive seconds, and there may be seconds in which neither server is upgraded. To avoid overloading a server while it is busy, a server is never upgraded during a second in which it receives a request: the first server receives a request during every second that is a multiple of req1 ; the second server receives a request during every second that is a multiple of req2 . A request only blocks the server that receives it. During a second that is a multiple of req1 but not of req2 , the second server may still be upgraded, and vice versa. The total time is the number of the last second in wh