Special Offers
- Acquire a Source of Open Access (OA) APC Funding for Your Institution Through
  IGI Global's OA Fee Waiver (Offset Model) Initiative
  For any library that invests in IGI Global's InfoSci-Books and/or InfoSci-Journals databases, IGI Global will match the library’s investment with a fund of equal value to go toward subsidizing the OA APCs for their faculty patrons when their work is submitted/accepted under OA into an IGI Global journal.
  Learn More
- Subscribe to the Latest Research Through IGI Global's InfoSci-OnDemand Plus
  InfoSci®-OnDemand Plus, a subscription-based service, provides researchers the ability to access full-text content from over 100,000+ peer-reviewed book chapters and 25,000+ scholarly journal articles that spans across 350+ topics in 11 core subjects. Users can select articles or chapters that meet their interests and gain access to the full content permanently in their personal online InfoSci-OnDemand Plus library.
  Subscribe
- Purchase the Encyclopedia of Information Science and Technology, Fourth Edition
  and Receive Complimentary E-Books of Previous Editions
  When ordering directly through IGI Global's Online Bookstore, receive the complimentary e-books for the first, second, and third editions with the purchase of the Encyclopedia of Information Science and Technology, Fourth Edition e-book.
  Purchase
- Create a Free IGI Global Library Account to Receive an Additional 5% Discount on All Purchases
  Exclusive benefits include one-click shopping, flexible payment options, free COUNTER 5 reports and MARC records, and a 5% discount on single all titles, as well as the award-winning InfoSci^®-Databases.
  Sign Up Now!
- Receive a 20% Discount on All Publications Purchased Through
  IGI Global’s Online Bookstore
  This discount cannot be combined with any other offer and is only valid when purchasing directly through IGI Global. (Exclusion of select titles and products may apply).
  Browse Publications
Books
Journals
InfoSci^®-Databases
Articles/Chapters
Publish with Us
Resources
- - Instructors
  - Course Adoption
  - Teaching Cases
  - Researchers
  - Browse Books
  - Browse Journals
  - Search Open Access Content
  - Streaming Videos
  - OnDemand Downloads
  - Webinars
  - Authors and Editors
  - eEditorial Discovery^® System
  - Peer Review Process
  - Ethics and Malpractice
  - Fair Use Policy
  - Open Access Publishing
  - Editorial Services
  - FAQ
  - Distributors
  - Distributor Resources
  - Book Distributors
  - Journal Subscription Agencies
  - E-Resource Partners
Catalogs
About Us
Newsroom

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)

Source Title: International Journal of Green Computing (IJGC) 2(2)

DOI: 10.4018/jgc.2011070101

OnDemand PDF Download:

$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.

Article Preview

Top

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