INTRODUCTION TO OPERATIONS RESEARCH - IIM …

1 INTRODUCTION TOOPERATIONS RESEARCHN inth EditionFREDERICK S. HILLIERS tanford UniversityGERALD J. LIEBERMANLate of Stanford UniversityBODHIBRATA NAGI ndian Institute of Management CalcuttaPREETAM BASUI ndian Institute of Management CalcuttaTata McGraw Hill Education Private LimitedNEW DELHIMcGraw-Hill Offices New Delhi New York St Louis San Francisco Auckland Bogot Caracas Kuala Lumpur Lisbon London Madrid Mexico City Milan Montreal San Juan Santiago Singapore Sydney Tokyo 9/13/11 4:53 PM Page iiiTata McGraw-HillIntroduction to OPERATIONS RESEARCH , 9eIndian Adaptation done by arrangement with the McGraw-Hill Companies, Inc.

2 , New YorkSales Territories: India, Pakistan, Nepal, Bangladesh, Sri Lanka and BhutanCopyright 2012, by The McGraw-Hill Companies, Inc. All Rights reserved. No part of this publication may be repro-duced or distributed in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise or stored in a database or retrieval system without the prior written permission of The McGraw-Hill Companies, 1221 Avenue of the Americas, New York, NY, 10020 including, but not limited to, in any network or other electronic storage or transmis-sion, or broadcast for distance McGraw-Hill Edition 2012 ISBN-13: 978-0-07-133346-7 ISBN-10: 0-07-133346-0 Vice President and Managing Director McGraw-Hill Education: Asia Pacifi c Region: Ajay ShuklaHead Higher Education Publishing and Marketing: Vibha MahajanPublishing Manager B&E/HSSL.

3 Tapas K MajiDeputy Manager (Sponsoring): Surabhi KhareAssociate Acquisition Editor: Piyali GangulyDevelopment Editor: Anirudh SharanExecutive (Editorial Services): Yogesh KumarCopy Editor: Sampurna MajumderSenior Production Manager: Manohar LalSenior Production Executive: Atul GuptaMarketing Manager: Vijay SarathiAssistant Product Manager: Daisy SachdevaSenior Product Specialist: Anusha SharmaGraphic Designer (Cover Design): Meenu RaghavGeneral Manager Production: Rajender P GhanselaAssistant General Manager Production: B L DograInformation contained in this work has been obtained by Tata McGraw-Hill, from sources believed to be reliable. However, neither Tata McGraw-Hill nor its authors guarantee the accuracy or completeness of any information published herein, and neither Tata McGraw-Hill nor its authors shall be responsible for any errors, omissions, or damages arising out of use of this information.

4 This work is published with the understanding that Tata McGraw-Hill and its authors are supplying information but are not attempting to render engineering or other professional services. If such services are required, the assistance of an appropriate professional should be by the Tata McGraw Hill Education Private Limited, 7 West Patel Nagar, New Delhi 110 008,Typeset at The Composers, 260, Apt., Paschim Vihar, New Delhi 110 063 and printed atIndia Binding House, A-98, Sector - 65, Noida, Printer: India Binding House** 9/13/11 4:53 PM Page ivFrederick S. Hillierwas born and raised in Aberdeen, Washington, where he was an award winner instatewide high school contests in essay writing, mathematics, debate, and music.

5 As an undergraduate atStanford University he ranked first in his engineering class of over 300 students. He also won the McKinseyPrize for technical writing, won the Outstanding Sophomore Debater award, played in the StanfordWoodwind Quintet, and won the Hamilton Award for combining excellence in engineering with notableachievements in the humanities and social sciences. Upon his graduation with a degree in IndustrialEngineering, he was awarded three national fellowships (National Science Foundation, Tau Beta Pi, andDanforth) for graduate study at Stanford with specialization in OPERATIONS RESEARCH . After receiving his PhDdegree, he joined the faculty of Stanford University, where he earned tenure at the age of 28 and the rank offull professor at 32.

6 He also received visiting appointments at CornellUniversity, Carnegie-MellonUniversity, the Technical University of Denmark, the University of Canterbury (New Zealand), and theUniversity of Cambridge (England). After 35 years on the Stanford faculty, he took early retirement fromhis faculty responsibilities in 1996 in order to focus full time on textbook writing, and now is ProfessorEmeritus of OPERATIONS RESEARCH at Hillier s RESEARCH has extended into a variety of areas, including integer programming,queueingtheory and its application, statistical quality control, and the application of OPERATIONS RESEARCH to the design ofproduction systems and to capital budgeting.

7 He has published widely, and his seminal papers have beenselected for republication in books of selected readings at least 10 times. He was the first-prize winner of aresearch contest on Capital Budgeting of Interrelated Projects sponsored by The Institute of ManagementSciences (TIMS) and the Office of Naval RESEARCH . He and Dr. Lieberman also received the honorablemention award for the 1995 Lanchester Prize (best English-language publication of any kind in the field ofoperations RESEARCH ), which was awarded by the Institute of OPERATIONS RESEARCH and the Management Sciences(INFORMS) for the 6th edition of this book. In addition, he was the recipient of the prestigious 2004 INFORMSE xpository Writing Award for the 8th edition of this Hillier has held many leadership positions with the professional societies in his field.

8 For example, hehas served as Treasurer of the OPERATIONS RESEARCH Society of America (ORSA), Vice President for Meetings ofTIMS, Co-General Chairman of the 1989 TIMS International Meeting in Osaka, Japan, Chair of the TIMSP ublications Committee, Chair of the ORSA Search Committee for Editor of OPERATIONS RESEARCH ,Chairof the ORSA Resources Planning Committee, Chair of the ORSA/TIMS Combined Meetings Committee,and Chair of the John von Neumann Theory Prize Selection Committee for INFORMS. He continues toserve as the Series Editor for Springer s International Series in OPERATIONS RESEARCH and ManagementScience, a particularly prominent book series that he founded in addition to INTRODUCTION to OPERATIONS Researchand two companion volumes, INTRODUCTION toMathematical Programming(2nd ed.)

9 , 1995) andIntroduction to Stochastic Models in OPERATIONS RESEARCH (1990), his books are The Evaluation of Risky Interrelated Investments(North-Holland, 1969),QueueingABOUT 9/13/11 4:53 PM Page vTables and Graphs(Elsevier North-Holland, 1981, co-authored by O. S. Yu, with D. M. Avis, L. D. Fossett,F. D. Lo, and M. I. Reiman), and INTRODUCTION to Management Science: A Modeling and Case StudiesApproach with Spreadsheets(3rd ed., McGraw-Hill/Irwin, 2008, co-authored by M. S. Hillier).The late Gerald J. Liebermansadly passed away in 1999. He had been Professor Emeritus of OperationsResearch and Statistics at Stanford University, where he was the founding chair of the Department ofOperations RESEARCH .

10 He was both an engineer (having received an undergraduate degree in mechanicalengineering from Cooper Union) and an OPERATIONS RESEARCH statistician (with an AM from Columbia Universityin mathematical statistics, and a PhD from Stanford University in statistics).Dr. Lieberman was one of Stanford s most eminent leaders in recent decades. After chairing theDepartment of OPERATIONS RESEARCH , he served as Associate Dean of the School of Humanities and Sciences,Vice Provost and Dean of RESEARCH , Vice Provost and Dean of Graduate Studies, Chair of the Faculty Senate,member of the University Advisory Board, and Chair of the Centennial Celebration Committee. He alsoserved as Provost or Acting Provost under three different Stanford these years of university leadership, he also remained active professionally.