Scheduling

PRINCIPLES OF SEQUENCING AND SCHEDULING

PRINCIPLES OF SEQUENCING AND SCHEDULING

Kenneth R. Baker
Tuck School of Business Dartmouth College Hanover, New Hampshire

Dan Trietsch
College of Engineering American University of Armenia Yerevan, Armenia

A JOHN WILEY & SONS, INC. PUBLICATION

Copyright

C

2009 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc.,Hoboken, New Jersey. Published simultaneously in Canada. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, orauthorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201)748-6008, or online at http://www.wiley.com/go/permissions. Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particularpurpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental,consequential, or other damages. For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronicformats. For more information about Wiley products, visit our web site at www.wiley.com. Library of Congress Cataloging-in-Publication Data: Baker, Kenneth R., 1943 – Principles of sequencing and scheduling / Kenneth R. Baker, Dan Trietsch. p. cm. Includes bibliographical references and index. ISBN 978-0-470-39165-5 (cloth) 1. Production scheduling. I. Trietsch, Dan. II. Title. TS157.5.B35 2009658.5 3–dc22 2008041829 Printed in the United States of America 10 9 8 7 6 5 4 3 2 1

CONTENTS

Preface 1 Introduction 1.1 Introduction to Sequencing and Scheduling, 1 1.2 Scheduling Theory, 3 1.3 Philosophy and Coverage of the Book, 6 References, 8 2 Single-Machine Sequencing 2.1 Introduction, 10 2.2 Preliminaries, 11 2.3 Problems Without Due Dates: Elementary Results, 15 2.3.1 Flowtime andInventory, 15 2.3.2 Minimizing Total Flowtime, 16 2.3.3 Minimizing Total Weighted Flowtime, 19 2.4 Problems with Due Dates: Elementary Results, 21 2.4.1 Lateness Criteria, 21 2.4.2 Minimizing the Number of Tardy Jobs, 24 2.4.3 Minimizing Total Tardiness, 25 2.4.4 Due Dates as Decisions, 29 2.5 Summary, 31 References, 31 Exercises, 32

xiii 1

10

v

vi

CONTENTS

3 Optimization Methods for theSingle-Machine Problem 3.1 3.2 3.3 3.4 3.5 3.6 Introduction, 34 Adjacent Pairwise Interchange Methods, 36 A Dynamic Programming Approach, 37 Dominance Properties, 43 A Branch and Bound Approach, 47 Summary, 53 References, 55 Exercises, 55

34

4 Heuristic Methods for the Single-Machine Problem 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 Introduction, 57 Dispatching and Construction Procedures, 58 Random...