Theoretical Analysis on Powers-of-Two Applied to JSP: A Case Study of Turbine Manufacturing

Theoretical Analysis on Powers-of-Two Applied to JSP: A Case Study of Turbine Manufacturing

V. Mahesh (S. R. Engineering College, India), L. Siva Rama Krishna (Osmania University, India), Sandeep Dulluri (IBM India Pvt. Ltd, India) and C. S. P. Rao (National Institute of Technology, Warangal, India)
Copyright: © 2013 |Pages: 21
DOI: 10.4018/978-1-4666-2646-1.ch007

Abstract

This paper discusses the scheduling of precedence-related jobs non-preemptively in a job shop environment with an objective of minimizing the makespan. Due to the NP-hard nature of the scheduling problems, it is usually difficult to find an exact optimal schedule and hence one should rely on finding a near to optimal solution. This paper proposes a computationally effective powers-of-two heuristic for solving job shop scheduling problem. The authors prove that the makespan obtained through powers-of-two release dates lies within 6% of the optimal value. The authors also prove the efficacy of powers-of-two approach through mathematical induction.
Chapter Preview
Top

Job Shop Schedule

An instance of a job shop scheduling problem consists of a collection of jobs978-1-4666-2646-1.ch007.m01which are weighted according to their importance. The time when a job 978-1-4666-2646-1.ch007.m02arrives is its release time and is denoted by978-1-4666-2646-1.ch007.m03 Each job is composed of a set of operations978-1-4666-2646-1.ch007.m04 The processing time associated with each operation is978-1-4666-2646-1.ch007.m05 The execution of each operation 978-1-4666-2646-1.ch007.m06 requires the use of a set of machines978-1-4666-2646-1.ch007.m07 Precedence’s are imposed on the set 978-1-4666-2646-1.ch007.m08using a binary relation A. If978-1-4666-2646-1.ch007.m09 then 978-1-4666-2646-1.ch007.m10has to be performed before978-1-4666-2646-1.ch007.m11 Schedule is a function that defines the start time for each operation 978-1-4666-2646-1.ch007.m12i.e., 978-1-4666-2646-1.ch007.m13

Complete Chapter List

Search this Book:
Reset