Complexity on Parallel Machine Scheduling: A Review
The intended audience is scheduling practitioners and theoreticians as well as beginners in the field of scheduling. The purpose of this paper is to review the area of parallel machine scheduling (PMS) on issues of complexity. A critical review of the met
- PDF / 359,979 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 202 Views
Abstract The intended audience is scheduling practitioners and theoreticians as well as beginners in the field of scheduling. The purpose of this paper is to review the area of parallel machine scheduling (PMS) on issues of complexity. A critical review of the methods employed and applications developed in this relatively new area are presented and notable successes are highlighted. The PMS algorithms are discussed. We have given up-to-date information on polynomially type of problems based on non-preemptive criteria. It is shown that parallel machine makespan-minimization problem is NP-hard even for the two-machine problem. Moreover, the two-machine problem can be solved by the pseudo polynomial algorithm. Keywords Parallel machine • Scheduling • Non-preemptive • Makespan • Polynomial • Complexity
1 Introduction In the twenty-first century, the scheduling research area has made extraordinary advances in the development of techniques that enable improved solutions to practical problems [1, 2]. Notwithstanding the strengths of current techniques, the problems being addressed by current scheduling methods are generally NP-hard and solved only approximately [3]; there is scope for improvement in techniques for accommodating different classes of constraints and for optimizing under different sets of objective criteria [4–7]. The running time or time complexity of an algorithm expresses the total number of elementary operations, such as additions, multiplications, and comparisons, for each possible problem instance as a function of the size of the instance. The input size of a typical scheduling problem is bounded by the number of jobs n, the number of machines m and the number of bits to represent
D. K. Behera (*) Mechanical Engineering Department, Jadavpur University, Kolkata 700032, India e-mail: [email protected]
S. Sathiyamoorthy et al. (eds.), Emerging Trends in Science, Engineering and Technology, Lecture Notes in Mechanical Engineering, DOI: 10.1007/978-81-322-1007-8_34, © Springer India 2012
373
D. K. Behera
374
the largest integer (the processing time, tardiness, the due date etc.,). An algorithm is said to be polynomial or a polynomial-time algorithm, if its running time is bounded by a polynomial in input size [3–7]. The most real-world problems are difficult to solve to optimality [3, 7–9]. So, Polynomial-time algorithms (PTA) was introduced by Cobham in year 1964 in deterministic machine models and later by Edmonds in 1965 saying that polynomial time represents efficient computation. An algorithm with rational input is said to run in polynomial time if there is an integer say k such that it runs in O (nk) times where n is the given input size, and all numbers in intermediate computations can be stored with O (nk) bits. We term it as a linear-time algorithm when the value of k becomes unit. PTA are persistently called “efficient” or “good”. This big O notation is used to classify algorithms by how they respond (based on processing time requirements) to changes in input factor or
Data Loading...
