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

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

Job Shop Schedule

An instance of a job shop scheduling problem consists of a collection of jobs which are weighted according to their importance. The time when a job arrives is its release time and is denoted by. Each job is composed of a set of operations. The processing time associated with each operation is. The execution of each operation requires the use of a set of machines. Precedence’s are imposed on the set using a binary relation A. If, then has to be performed before. Schedule is a function that defines the start time for each operation i.e., .

Purchase this article to continue reading all 20 pages >

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 2 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 2 Issues (2018): 1 Released, 1 Forthcoming
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