Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> This paper considers the problem of preemptive on-line scheduling for two uniform processors in which one of the processors has speed 1 and the other has speed s>=1. The objective is to minimize the makespan. A best possible algorithm with competitive ratio of (1+s)^2/(1+s+s^2) is proposed for this problem. <s> BIB001 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> We consider the problem of scheduling N jobs on M parallel machines that operate at different speeds (known as uniform parallel machines), to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidentical due dates. Violations of due dates result in earliness or tardiness penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero–one variables than typical formulations for scheduling problems of this type. We present our computational experience in using this model to solve small sized problems, and discuss solution approaches for solving larger problems. ::: ::: ::: Scope and purpose ::: ::: In JIT environments, firms face the need to complete jobs as close to their due dates as possible. Failure to do so would result in earliness and/or tardiness costs and the optimum schedule would seek to minimize functions of these costs. In many real-world situations, the problem is greatly complicated by the presence of disparate issues such as: (i) uniform parallel machines that are capable of processing these jobs at different speeds; (ii) sequence-dependent setup times; (iii) distinct job due dates; (iv) distinct job ready dates; and (v) distinct earliness and/or tardiness costs for each job. For this complex problem, we present a compact mathematical model and describe our computational experience in using this model to solve small sized problems. <s> BIB002 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> We study preemptive scheduling on uniformly related processors, where jobs are arriving one by one in an on-line fashion. We consider the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, we design an algorithm of optimal competitive ratio. This generalizes the known result for identical machines, and solves other interesting cases. <s> BIB003 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> We study preemptive scheduling on uniformly related processors, where jobs are arriving one by one in an on-line fashion. We consider the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, we design an algorithm of optimal competitive ratio. This generalizes the known result for identical machines, and solves other interesting cases. <s> BIB004 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> Abstract We study a preemptive semi-online scheduling problem. Jobs with non-increasing sizes arrive one by one to be scheduled on two uniformly related machines. We analyze the algorithms as a function of the speed ratio (q⩾1) between the two machines. We design algorithms of optimal competitive ratio for all values of q, and show that for q>2, idle time needs to be introduced. This is the first preemptive scheduling problem over list, where idle time is provably required. <s> BIB005 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r≥1 ) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s≥1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms. <s> BIB006 </s> Literature Review of Single Machine Scheduling Problem with Uniform Parallel Machines <s> Online Scheduling of Preemptive Jobs to <s> In this paper, we consider the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ [1, ∞), and show that idle time is required during the assignment procedure of algorithms for any s > √6/2. The competitive ratios of the algorithms match the randomized lower bound for every 1 ≤ s ≤ 3. The problem of whether randomization still does not help for the discussed preemptive scheduling problem remains open. <s> BIB007
Minimize Makespan Wen and Du BIB001 have considered the problem of pre-emptive on-line scheduling for two processors in which one of the processors has speed 1 and the speed of the other processor is greater than or equal to 1. In this research, the objective is to minimize the makespan. They proposed an algorithm with competitive ratio of (1+s) 2 / (1+s+s 2 ) for this problem. Vestjens  considered the online scheduling problem in which n jobs, where n is unknown are to be scheduled on m uniform parallel machines with preemption of jobs such that the makespan is minimized. The processing time of the job is known on its arrival. The author has shown that if only a finite number of preemptions is allowed, then there exists an algorithm that solves the problem if and only if s i-1 /s i ≤ s i /s i+1 for all i = 2, …, m-1, s i is the largest machine speed. It is shown that if this condition is to be satisfied, then O(mn) preemptions are necessary. Epstein, Noga, Seiden, Sgall and Woeginger  [68], studied the problem of on-line scheduling on two uniform machines with speeds 1 and s ≥ 1. Here, the objective is to obtain a schedule, which minimizes the makespan. First, they presented randomized results for this problem. Then, they showed a simple memory-less algorithm with competitive ratio (4-s)(1+s)/4 ≤ 1.5625. Also, they analyzed other randomized algorithms which demonstrate that the randomized competitive ratio is at most 1.52778 for any s. Finally, they presented a deterministic algorithm with competitive ratio of 1+s/(s 2 + s + 1) for the preemptive version of this problem. Epstein BIB003 BIB004 studied the preemptive scheduling on uniformly related processors, where jobs are assigned one by one in an on-line fashion such that the makespan is minimized. This paper discusses the class of machine sets where the speed ratios are non-decreasing as speed increases. For each set of machines in this class, an algorithm of optimal competitive ratio is deigned in this paper. This generalizes the known result for identical machines and solves other interesting cases. A study on preemptive semi-online scheduling was carried out by Epstein and Favrholdt BIB005 . In this study, jobs with non-increasing sizes arrive one by one which are to be scheduled on two uniformly related machines. They analyzed the algorithms as a function of the speed ratio (s ≥ 1) between the two machines. Here, the objective is to minimize the makespan. Then, they designed algorithms of optimal completive ratio for all values of s and showed that for s > 2, idle time needs to be introduced. This is the first preemptive scheduling problem over list, where idle time is provably required. Donglei Du BIB006 also investigated the same problem within a certain range [1,r] (r ≥ 1) with the objective of minimizing the makespan. The author has characterized the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm. The researchers have concentrated on the development of algorithms with different competitive ratios. In future, researchers may aim to develop algorithms which yield better competitive ratio. Minimize Sum of Tardiness/Earliness Balakrishnan, Kanet and Sridharan BIB002 have researched the problem of scheduling jobs uniform parallel machines to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner and have non-identical due dates. Any job completion beyond its due date results in earliness or tardiness penalty, which may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, they presented a mixed integer formulation that has substantially fewer zero-one variables than typical formulations for scheduling problems of this type. They have reported their computational experience in using this model to solve small size problems and presented solution procedures for solving larger size problems. Bilge, Kirac, Kurtulan and Pekgun  have considered the problem of scheduling a set of dependent jobs with sequence dependent setups on a set of uniform parallel machines such that the total tardiness is minimized. Jobs have non-identical due dates and arrival times. They have used tabu search based algorithm for this problem. They have used several key components of tabu search such as candidate list strategies, tabu classifications, tabu tenure and intensification and diversification strategies in their algorithm. Alternate approaches to each of these issues are developed and extensively tested on a set of problems obtained from the literature. The results obtained are considerably better than those reported previously and constitute the best solutions known for the benchmark problems up to date. As stated earlier, the minimization of the total earliness/tardiness is considered to be a challenging measure of performance even in the single machine scheduling problem with single processor. This magnifies the complexity of the algorithm to obtain the optimal solution. The researchers have concentrated on the development of mathematical model and tabu search based algorithm for this problem. As mentioned earlier, since it is a challenging measure magnifying the complexity of the problem, use of any model will take too much computational time. So, the researchers should concentrate on the development of meta-heuristics to obtain near-optimal/global optimum solutions for this scheduling problem. Maximize Minimum Completion Time (Machine Covering Problem) He and Jiang BIB007 considered the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. The goal of this paper is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. They designed optimal deterministic semi-online algorithms for every machine speed ratio s in the range from 1 to ∞ and showed that idle time is required during the assignment procedure of algorithms for any s greater than √6/2.The competitive ratio ratios of the algorithms match the randomized lower bound for every s in the range from 1 to 3. A very few researchers have concentrated on this problem on the development of algorithms and analysis of competitive ratio. In future, researchers may aim to develop algorithms which yield better competitive ratio.