Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Preemptive Jobs <s> This paper considers a scheduling problem whose objective is to determine both the optimal speeds of processors and an optimal schedule in a preemptive multiprocessor environment. The jobs are independent and each processor can be assigned any speed; however, the cost associated with each processor is a function of the processor's speed. Polynomial algorithms are presented to find optimal speed assignments for a variety of cost functions. <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Preemptive Jobs <s> Abstract The problem of minimizing mean weighted execution time loss was formulated by the present author in 1984; there the preemptive case for identical as well as for a fixed number of uniform processors was solved via a linear programming approach. In this paper, we propose a strongly polynomial algorithm based on a network flow technique, which minimizes the above criterion for an arbitrary number of identical as well as uniform processors. The upper bounds on the number of preemptions in both cases are also given. <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Preemptive Jobs <s> We present an optimal algorithm for scheduling a complete k-ary tree on two uniform processors of different speeds in order to minimize schedule length. We consider the basic case of unit standard execution times and unit communication times. <s> BIB003 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Preemptive Jobs <s> We show that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize makespan is NP-hard in the strong sense. We also give a heuristic that generates solutions with known, and relatively small, absolute error for this problem. The NP-hardness result holds even for the case without communication delays, and complements the earlier result of Gonzalez and Sahni who gave a polynomial time algorithm for preemptive jobs of arbitrary length. ::: ::: ::: ::: We also study the structure of optimal solutions for the two processor problem of scheduling chains of UET jobs with communication delays, where one processor is a (integer) times faster than the other. This investigation leads to a linear time optimization algorithm for this case. Copyright © 2002 John Wiley & Sons, Ltd. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Miscellaneous Problem with Preemptive Jobs <s> In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan. <s> BIB005
Blazewicz  has considered the problem of minimizing mean weighted information loss. In this paper, the preemptive case for identical as well as for a fixed number of uniform processors was considered. Blazewicz and Finke BIB002 have proposed a strongly polynomial algorithm based on a network flow technique, which minimizes the mean weighted execution time loss for an arbitrary number of identical processors as well as uniform processors. The upper bound on the number of preemptions in each of the cases is also reported. Ishi, martel, Masuda and Nishida BIB001 considered a scheduling problem in which the objective is to determine both the optimal speeds of processors and an optimal schedule in a preemptive multiprocessor environment. The jobs are independent and each processor can be assigned any speed. The cost associated with each processor is a function of the speed of the processor. They presented polynomial algorithms to find the optimal speed assignments for a variety of cost functions such that the total cost is minimized in each case. Blazewicz, Bouvry, Guinand and Trystram BIB003 presented an optimal algorithm for scheduling a complete k-ary tree on two uniform processors of different speeds in order to minimize the makespan. They considered the basic case of unit standard execution times and unit communication times. Shakhlevich and Strusevich BIB005 have provided a unified approach to solve preemptive scheduling problems with uniform parallel machines and controllable processing times. They demonstrated that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatriod. This justified the applicability of the greedy approach and allowed them to develop fast algorithms for solving the special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem, they developed an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makepsan. Kubiak, Penz and Trystram BIB004 showed that the problem of scheduling chains of unit execution time (UET) jobs on uniform processors with communication delays to minimize the makespan is NP-hard in the strong sense. They also presented a heuristic that generates solutions with known and relatively small, absolute error for this problem. The NP-hardness result holds even for the case without communication delays and complements the earlier result of Gonzalez and Sahni  who gave a polynomial time algorithm for preemptive jobs of arbitrary length. They also studied the structure of optimal solutions for the two processor problem scheduling chains of UET jobs with communication delays, where one processor is an integer times faster than the other. This investigation resulted with a linear time optimization algorithm for this case.