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
OnDemand PDF Download:
$30.00
List Price: $37.50

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 jobswhich 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.,

Complete Chapter List

Search this Book:
Reset