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: © 2011 |Pages: 20
DOI: 10.4018/jgc.2011070101
OnDemand PDF Download:
No Current Special Offers


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.
Article Preview

Job Shop Schedule

An instance of a job shop scheduling problem consists of a collection of jobs jgc.2011070101.m01which are weighted according to their importance. The time when a job jgc.2011070101.m02arrives is its release time and is denoted byjgc.2011070101.m03. Each job is composed of a set of operationsjgc.2011070101.m04. The processing time associated with each operation isjgc.2011070101.m05. The execution of each operation jgc.2011070101.m06 requires the use of a set of machinesjgc.2011070101.m07. Precedence’s are imposed on the set jgc.2011070101.m08using a binary relation A. Ifjgc.2011070101.m09, then jgc.2011070101.m10has to be performed beforejgc.2011070101.m11. Schedule is a function that defines the start time for each operation jgc.2011070101.m12i.e., jgc.2011070101.m13.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 1 Issue (2019)
Volume 9: 2 Issues (2018)
Volume 8: 2 Issues (2017)
Volume 7: 1 Issue (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing