A review of four decades of timedependent scheduling: main results, new topics, and open problems This paper is a comprehensive review of the research conducted over the past four decades in the domain of timedependent scheduling, where variable processing times of jobs depend on when the jobs start. The paper is divided into four parts. The first part recalls some definitions and notions, introduces terminology, and defines the main models of timedependent job processing times and the notation that is used throughout the paper. The second part summarizes four decades of timedependent scheduling research, focusing on the computational complexity of timedependent scheduling problems, and algorithms solving these problems. The results are divided into groups with respect to the machine environment and illustrated by examples. The third part concentrates on new topics in timedependent scheduling, such as twoagent timedependent scheduling, mutually related timedependent scheduling problems, and timedependent scheduling games. The last part discusses the most important timedependent scheduling problems which still await solution. The paper is completed by bibliographic notes and an extensive list of references.

FixedOrder Scheduling on Parallel Machines We consider the following natural scheduling problem: Given a sequence of jobs with weights and processing times, one needs to assign each job to one of m identical machines in order to minimize the sum of weighted completion times. The twist is that for machine the jobs assigned to it must obey the order of the input sequence, as is the case in multiserver queuing systems. We establish a constant factor approximation algorithm for this (strongly NPhard) problem. Our approach is necessarily very different from what has been used for similar scheduling problems without the fixedorder assumption. We also give a QPTAS for the special case of unit processing times.