Search

The computational complexity of an algorithm is traditionally measured for the worst and the average case. The worst-case estimation guarantees a certain worst-case behavior of a given algorithm, although it might be rough, since in “most instances” the algorithm may have a significantly better performance. The probabilistic average-case analysis claims to derive an average performance of an algorithm, say, for an “average instance” of the problem in question. That instance may be far away from the average of the problem instances arising in a given real-life application, and so the average case analysis would also provide a non-realistic estimation. We suggest that, in general, a wider use of probabilistic models for a more accurate estimation of the algorithm efficiency could be possible. For instance, the quality of the solutions delivered by an approximation algorithm may also be estimated in the “average” probabilistic case. Such an approach would deal with the estimation of the quality of the solutions delivered by the algorithm for the most common (for a given application) problem instances. As we illustrate, the probabilistic modeling can also be used to derive an accurate time complexity performance measure, distinct from the traditional probabilistic average-case time complexity measure. Such an approach could, in particular, be useful when the traditional average-case estimation is still rough or is not possible at all.

We consider the multiprocessor job shop scheduling problem (JSP) with unrelated processors, an extension of the classical JSP. The precedence relations between the operations are given by an acyclic directed weighted graph, in which nodes represent operations and arcs represent precedence relations. The whole set of operations is partitioned into m subsets, and operations from kth subset have to be performed by any machine from the respective kth set of unrelated machines. The solution space of this generalized problem increases significantly as compared with that of the JSP. An algorithm is proposed, which drastically reduces this solution space. If we let ν and μ to be the number of operations and machines in each subset of operations and machines, then with a probability of almost 1, we generate approximately (µ)^mν and 2^m(µ−1) μ^mν times less feasible schedules than the number of all active feasible schedules of any corresponding instance of JSP and our generalized problem, respectively. Copyright © 2002 John Wiley & Sons, Ltd.

We consider the preemptive scheduling of nindependent jobs on munrelated machines to minimize the makespan. Preemptive schedules with at most 2m−3 preemptions are built, which are optimal when the maximal job processing time is no more than the optimal schedule makespan. We further restrict the maximal job processing time and obtain optimal schedules with at most m−1 preemptions. This is better than the earlier known best bound of 4m2−5m+2 on the total number of preemptions. Without the restriction on the maximal job processing time, our (2m−3)-preemptive schedules have a makespan which is no more than either of the following two magnitudes: (a) the maximum between the longest job processing time and the optimal preemptive makespan, and (b) the optimal nonpreemptive makespan. Our (m−1)-preemptive schedules might be at most twice worse than an optimal one.

The worst-case behavior of the “critical path” (CP) algorithm for multiprocessor scheduling with an out-tree task dependency structure is studied. The out-tree is not known in advance and the tasks are released on-line over time (each task is released at the completion time of its direct predecessor task in the out-tree). For each task, the processing time and the remainder (the length of the longest chain of the future tasks headed by this task) become known at its release time. The tight worst-case ratio and absolute error are derived for this strongly clairvoyant on-line model. For out-trees with a specific simple structure, essentially better worst-case ratio and absolute error are derived. Our bounds are given in terms of tmax, the length of the longest chain in the out-tree, and it is shown that the worst-case ratio asymptotically approaches 2 for large tmaxwhen the number of processors $$m=\widetilde {\tau}(\widetilde{\tau}+1)/2-2$$ , where $$\widetilde{\tau}$$ is an integer close to $$\sqrt {t_{\max}}$$ . A non-clairvoyant on-line version (without knowledge of task processing time and remainder at the release time of the task) is also considered and is shown that the worst-case behavior of width-first search is better or the same as that of the depth-first search.

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on a single machine. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e. processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. In our model preemption is not allowed, but we are allowed to restart a job, that is, the processing of a job can be broken off to have the machine available to process an urgent job, but the time already spent on processing this interrupted job is considered to be lost. We propose an on-line algorithm and show that its performance bound is equal to 1.5, which matches a known lower bound due to Vestjens. For the same problem without restarts the optimal worst-case bound is known to be equal to (\sqrt{5}+1)/2 \thickapprox 1.61803; this is the first example of a situation in which the possibility of applying restarts reduces the worst-case performance bound, even though the processing times are known. Copyright © 2000 John Wiley & Sons, Ltd.