The bin packing problem is a well-studied problem in combinatorial optimization. In the
classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to …

General: The machine load balancing problem is defined as follows: There are n parallel
machines and a number of independent tasks (jobs); the tasks arrive at arbitrary times …

In this chapter, we summarize research e orts on several di erent problems that fall under the
rubric of online scheduling. In online scheduling, the scheduler receives jobs that arrive over …

We study a classical problem in online scheduling. A sequence of jobs must be scheduled
on m identical parallel machines. As each job arrives, its processing time is known. The goal …

The partition problem is one of the basic NP-complete problems. While an efficient heuristic
for the optimization version, which is equivalent to minimizing the makespan on two identical …

In the classical version of the bin packing problem one is given a list L=(a 1,..., an) of items
(or elements) and an infinite supply of bins with capacity C. A function s (ai) gives the size of …

We consider the online multiprocessor scheduling problem first considered by Graham in
1966 which can be formulated as the following online load-balancing problem: a set of jobs …

We present a new on‐line algorithm, MR, for non‐preemptive scheduling of jobs with known
processing times on m identical machines which beats the best previous algorithm for m⩾ …

The problem considered here is the same as the one discussed in G. Galambos and GJ
Woeginger, eds., SIAM J. Comput., 22 (1993), pp. 349--355. It is an m-machine online …

In (Ref. 1),(Ref. 2) it was noticed that sometimes it takes BGP a substantial amount of time
and messages to converge and stabilize following the failure of some node in the Internet. In …