Minimizing Total Flow Time and Total Completion Time with Immediate Dispatching

We consider the problem of scheduling jobs arriving over time in a multiprocessor setting, with immediate dispatching, disallowing job migration. The goal is to minimize both the total flow time (total time in the system) and the total completion time. Previous studies have shown that while preemption (interrupt a job and later continue its execution) is inherent to make a scheduling algorithm efficient, migration (continue the execution on a different machine) is not. Still, the current non-migratory online algorithms suffer from a need for a central queue of unassigned jobs which is a "no option" in large computing systems, such as the Web. We introduce a simple online non-migratory algorithm IMD, which employs immediate dispatching, i.e., it immediately assigns released jobs to one of the machines. We show that the performance of this algorithm is within a logarithmic factor of the optimal migratory offline algorithm, with respect to the total flow time, and within a small constant factor of the optimal migratory offline algorithm, with respect to the total completion time. This solves an open problem suggested by Awerbuch et al. (STOC 99).     

APPLICATION OF MULTIVARIABLE CONTROL DESIGN TO DUAL‐MODE DIGITAL VERSATILE DISC DRIVE

With the ever increasing demand for on storage media with more memory and faster speeds, Digital Versatile Disc (DVD) appears to eclipse Compact Discs (CD). Its denser track pitch and shorter minimum pit length allows for at least eight time more storage memory in the same area. However, smaller tracks increase the performance demands placed on control algorithms. Moreover, to achieve shorter read times, higher disc rotation speed is required, further increasing the demands on the controller. Classical single‐loop control design techniques, the usual approach used in such applications, become less effective for DVDs and may even fail to yield a design for higher disc speeds and with increased coupling in the mechanism's dynamics. For this purpose, we employ the Quantitative Feedback Theory (QFT) and specialized graphical user interface to experimentally demonstrate that new design tools can accomplish the task. Specifically, we show that our multivariable design approach can cope with performance robustness issues and achieve back‐compatibility for dual use (i.e. play both CD and DVD discs) in a single drive. Moreover, since QFT can be used with direct frequency response measurements to represent the dynamics, our control tuning procedure facilitates fast and efficient use in an industrial setting so as to minimize the time it takes to bring new products to market.     

Maximizing throughput in multi-queue switches

We study a basic problem in Multi-Queue switches. A switch connectsm input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacityB. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g. IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [5] for arbitraryB. Recently, a (17/9 ≈ 1.89)-competitive algorithm was presented forB>1 in [3]. Our main result in this paper shows that forB which is not too small our algorithm can do better than 1.89, and approach a competitive ratio ofe/(e − 1) ≈ 1.58. The research of Yossi Azar was supported in part by the Israeli Ministry of Industry and Trade and by the Israel Science Foundation.