Scheduling in Supply Chains Using Mixed Integer Programming E-Book

Tadeusz Sawik

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 655

Veröffentlichungsjahr: 2011

Beschreibung

A unified, systematic approach to applying mixed integer programming solutions to integrated scheduling in customer-driven supply chains

Supply chain management is a rapidly developing field, and the recent improvements in modeling, preprocessing, solution algorithms, and mixed integer programming (MIP) software have made it possible to solve large-scale MIP models of scheduling problems, especially integrated scheduling in supply chains. Featuring a unified and systematic presentation, Scheduling in Supply Chains Using Mixed Integer Programming provides state-of-the-art MIP modeling and solutions approaches, equipping readers with the knowledge and tools to model and solve real-world supply chain scheduling problems in make-to-order manufacturing.

Drawing upon the author's own research, the book explores MIP approaches and examples-which are modeled on actual supply chain scheduling problems in high-tech industries-in three comprehensive sections:

• Short-Term Scheduling in Supply Chains presents various MIP models and provides heuristic algorithms for scheduling flexible flow shops and surface mount technology lines, balancing and scheduling of Flexible Assembly Lines, and loading and scheduling of Flexible Assembly Systems
• Medium-Term Scheduling in Supply Chains outlines MIP models and MIP-based heuristic algorithms for supplier selection and order allocation, customer order acceptance and due date setting, material supply scheduling, and medium-term scheduling and rescheduling of customer orders in a make-to-order discrete manufacturing environment
• Coordinated Scheduling in Supply Chains explores coordinated scheduling of manufacturing and supply of parts as well as the assembly of products in supply chains with a single producer and single or multiple suppliers; MIP models for a single- or multiple-objective decision making are also provided

Two main decision-making approaches are discussed and compared throughout. The integrated (simultaneous) approach, in which all required decisions are made simultaneously using complex, monolithic MIP models; and the hierarchical (sequential) approach, in which the required decisions are made successively using hierarchies of simpler and smaller-sized MIP models. Throughout the book, the author provides insight on the presented modeling tools using AMPL® modeling language and CPLEX solver.

Scheduling in Supply Chains Using Mixed Integer Programming is a comprehensive resource for practitioners and researchers working in supply chain planning, scheduling, and management. The book is also appropriate for graduate- and PhD-level courses on supply chains for students majoring in management science, industrial engineering, operations research, applied mathematics, and computer science.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Dedication

List of Figures

List of Tables

Preface

Acknowledgments

Introduction

Outline of the Book

Part One: Short-Term Scheduling in Supply Chains

Chapter 1: Scheduling of Flexible Flow Shops

1.1 Introduction

1.2 Mixed Integer Programs for Scheduling Flow Shops

1.3 Constructive Heuristics for Scheduling Flexible Flow Shops

1.4 Scheduling Flow Shops With Limited Machine Availability

1.5 Computational Examples

1.6 Comments

Exercises

Chapter 2: Scheduling of Surface Mount Technology Lines

2.1 Introduction

2.2 SMT Line Configurations

2.3 General Scheduling of SMT Lines

2.4 Batch Scheduling of SMT Lines

2.5 An Improvement Heuristic for Scheduling SMT Lines

2.6 Computational Examples

2.7 Comments

Exercises

Chapter 3: Balancing and Scheduling of Flexible Assembly Lines

3.1 Introduction

3.2 Balancing and Scheduling of Flexible Assembly Lines with Infinite In-Process Buffers

3.3 Balancing and Scheduling of SMT Lines

3.4 Comments

Exercises

Chapter 4: Loading and Scheduling of Flexible Assembly Systems

4.1 Introduction

4.2 Loading and Scheduling of Flexible Assembly Systems with Single Stations and Infinite In-Process Buffers

4.3 Loading and Scheduling of Flexible Assembly Systems with Parallel Stations and Finite In-Process Buffers

4.4 Comments

Exercises

Part Two: Medium-Term Scheduling in Supply Chains

Chapter 5: Customer Order Acceptance and Due Date Setting in Make-to-Order Manufacturing

5.1 Introduction

5.2 Problem Description

5.3 Bi-Objective Order Acceptance and Due Date Setting

5.4 Lexicographic Approach

5.5 Scheduling of Customer Orders

5.6 Computational Examples

5.7 Comments

Exercises

Chapter 6: Aggregate Production Scheduling in Make-to-Order Manufacturing

6.1 Introduction

6.2 Problem Description

6.3 Bi-Objective Scheduling of Customer Orders

6.4 Multi-Objective Scheduling of Customer Orders

6.5 Scheduling of Single-Period Customer Orders

6.6 Comments

Exercises

Chapter 7: Reactive Aggregate Production Scheduling in Make-to-Order Manufacturing

7.1 Introduction

7.2 Problem Description

7.3 Mixed Integer Programs for Reactive Scheduling

7.4 Rescheduling Algorithms

7.5 Input and Output Inventory

7.6 Computational Examples

7.7 Comments

Exercises

Chapter 8: Scheduling of Material Supplies in Make-to-Order Manufacturing

8.1 Introduction

8.2 Flexible vs. Cyclic Material Supplies

8.3 Model Enhancements

8.4 Computational Examples

8.5 Comments

Exercises

Chapter 9: Selection of Static Supply Portfolio in Supply Chains with Risks

9.1 Introduction

9.2 Selection of a Supply Portfolio without Discount Under Operational Risks

9.3 Selection of Supply Portfolio with Discount Under Operational Risks

9.4 Computational Examples

9.5 Selection of Supply Portfolio Under Disruption Risks

9.6 Single-Objective Supply Portfolio Under Disruption Risks

9.7 Bi-Objective Supply Portfolio Under Disruption Risks

9.8 Computational Examples

9.9 Comments

Exercises

Chapter 10: Selection of a Dynamic Supply Portfolio in Supply Chains with Risks

10.1 Introduction

10.2 Multiperiod Supplier Selection and Order Allocation

10.3 Selection of a Dynamic Supply Portfolio to Minimize Expected Costs

10.4 Selection of a Dynamic Supply Portfolio to Minimize Expected Worst-Case Costs

10.5 Supply Portfolio For Best-Case and Worst-Case TDN Supplies

10.6 Computational Examples

10.7 Comments

Exercises

Part Three: Coordinated Scheduling in Supply Chains

Chapter 11: Hierarchical Integration of Medium- and Short-Term Scheduling

11.1 Introduction

11.2 Problem Description

11.3 Medium-Term Production Scheduling

11.4 Short-Term Machine Assignment and Scheduling

11.5 Computational Examples

11.6 Comments

Exercises

Chapter 12: Coordinated Scheduling in Supply Chains with a Single Supplier

12.1 Introduction

12.2 Problem Description

12.3 Supply Chain Inventory

12.4 Coordinated Supply Chain Scheduling: An Integrated Approach

12.5 Coordinated Supply Chain Scheduling: A Hierarchical Approach

12.6 Computational Examples

12.7 Comments

Exercises

Chapter 13: Coordinated Scheduling in Supply Chains with Assignment of Orders to Suppliers

13.1 Introduction

13.2 Problem Description

13.3 Conditions for Feasibility of Customer Due Dates

13.4 Coordinated Supply Chain Scheduling: An Integrated Approach

13.5 Selected Multi-Objective Solution Approaches

13.6 Coordinated Supply Chain Scheduling: A Hierarchical Approach

13.7 Computational Examples

13.8 Comments

Exercises

Chapter 14: Coordinated Scheduling in Supply Chains

14.1 Introduction

14.2 Problem Description

14.3 Coordinated Supply Chain Scheduling: An Integrated Approach

14.4 Selected Bi-Objective Solution Approaches

14.5 Coordinated Supply Chain Scheduling: A Hierarchical Approach

14.6 Computational Examples

14.7 Comments

Exercises

References

Index

Scheduling in Supply Chains Using Mixed Integer Programming

Copyright © 2011 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished 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, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], 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, [phone], fax [phone], or online at http://www.wiley.com/go/pennission.

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 particular purpose. 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 [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Sawik, Tadeusz.Scheduling in supply chains using mixed integer programming / Tadeusz Sawik.p. cm.Includes bibliographical references and index.ISBN 978-0-470-93573-6 (cloth)1. Assembly-line methods—Data processing. 2. Business logistics—Data processing. 3. Production scheduling—Data processing. 4. Integer programming. I. Title.TS178.4.S287 2011658.701′51977--dc22

2010047228

To Bartek,Kappa,Siasia, andToranoko with love,and to the memory ofmy parents

List of Tables

1.1 Notation: MIP Models for Scheduling Flexible Flow Shops

1.2 Notation: Heuristic Algorithms

1.3 A Heuristic Schedule

1.4 Characteristics of FPB/FPBD Models and Solution Results

1.5 Relative Increase of Makespan

2.1 Characteristics of Various SMT Line Configurations

2.2 Notation: MIP Models for Scheduling SMT Lines

2.3 Processing Times for an SMT Line with Parallel Stations

2.4 Processing Times for an SMT Line with a Dual Conveyor

2.5 Example 3: Processing Times

2.6 Example 3: Input Data

2.7 Example 3: MIP Results for Daily Mix

2.8 Example 4: Processing Times

2.9 Example 4: Input Data

2.10 Example 4: Heuristic Results for Daily Mix/MPS

2.11 Example 4: MIP Results for MPS

2.12 Projected Impact of SMT Line Modifications

3.1 Notation: Balancing and Scheduling of FAL with Infinite In-Process Buffers

3.2 Influence of the Work Space Constraints

3.3 Computational Results: Integrated vs. Hierarchical Approach

3.4 Notation: Balancing and Scheduling of SMT Lines

3.5 Component Sizes and Placement Times

3.6 Processing Times for Simultaneous Balancing and Scheduling

3.7 Processing Times for Two-Level Balancing and Scheduling

3.8 Characteristics of MIP Models and Solution Results

4.1 Notation: Loading and Scheduling of an FAS with Infinite In-Process Buffers

4.2 Notation: Loading and Scheduling of an FAS with Finite In-Process Buffers

4.3 Solution Results for the Example Problems

5.1 Notation: Order Acceptance and Due Date Setting

5.2 Computational Results: Model DDS

5.3 Computational Results: Model SCOI

5.4 Computational Results: Ex Post Solutions

6.1 Notation: Aggregate Production Scheduling

6.2 Computational Results for Scenario I: Model OA

6.3 Computational Results for Scenario I: Model IL

6.4 Computational Results for Scenario I: Model ILE

6.5 Computational Results for Scenario I: Model PL

6.6 Computational Results for Scenario II: Model OA

6.7 Computational Results for Scenario II: Model IL

6.8 Computational Results for Scenario II: Model ILE

6.9 Computational Results for Scenario II: Model PL

6.10 Minimum Capacity of Input, Output, and Central Buffers for Scenario II

6.11 Minimum Number of Tardy Orders vs. Maximum Earliness for Scenario II

6.12 Minimum Capacity of the Output Buffer

6.13 Computational Results for Scenario I

6.14 Computational Results for Scenario II

6.15 Computational Results for Scenario II: Basic Integer Program OA1

6.16 Distribution of Customer Orders for Increasing Demand Pattern: Scenario I

6.17 Optimal Assignment of Customer Orders for min Pmax Criterion

6.18 Optimal Assignment of Customer Orders for max Pmin Criterion

7.1 Notation: Initial Scheduling

7.2 Notation: Rescheduling

7.3 Computational Results for Scenario A

7.4 Computational Results for Scenario B

7.5 Computational Results for Scenario C

8.1 Notation: Scheduling of Material Supplies

8.2 Aggregate Production Schedule nlt

8.3 Supplies of Common Materials vkt: Flexible Approach

8.4 Supplies of Product-Specific Materials vklt: Flexible Approach

8.5 Optimal Ordering Policy for Common Materials: Cyclic Approach

8.6 Optimal Ordering Policy for Product-Specific Materials: Cyclic Approach

9.1 Notation: Supply Portfolio without Discount

9.2 Notation: Supply Portfolio with Discount

9.3 Computational Results

9.4 Notation: Supply Portfolio under Disruption Risks

9.5 Solution Results for the SP_E Model

9.6 Solution Results for the SP_CV Model: Local Disruptions

9.7 Solution Results for the SP_CV Model: Local and Global Disruptions

9.8 Probability of Cost per Part for Optimal Supply Portfolios: Local and Global Disruptions

9.9 Solution Results for the SP_CV Model with Binary Assignment Variables zij

10.1 Notation: Dynamic Supply Portfolio

10.2 Decision Variables

10.3 Solution Results for Risk-Neutral Models

10.4 Solution Results for Risk-Averse Models

10.5 Solution Results for the TDN_CV Model: Special Scenarios

11.1 Notation: Medium-Term Production Scheduling

11.2 Notation: Short-Term Machine Assignment and Scheduling

11.3 Computational Results for Increasing Demand Pattern

11.4 Computational Results: Basic Integer Program MPS

11.5 Computational Results: Strengthened Integer Program MPS

12.1 Notation: Coordinated Scheduling in a Supply Chain with a Single Supplier

12.2 Computational Results: Integrated Approach

12.3 Computational Results: Hierarchical Approach

13.1 Notation: Multi-Objective Scheduling in a Supply Chain with Multiple Suppliers

13.2 Decision Variables: Multi-Objective Scheduling in a Supply Chain with Multiple Suppliers

13.3 Computational Results for the Monolithic Model INT: Weighted-Sum Program INTλ

13.4 Computational Results for the Monolithic Model INT: Lexicographic Approach

13.5 Computational Results for the Hierarchical Approach

14.1 Decision Variables: Bi-Objective Scheduling in a Supply Chain with Multiple Suppliers

14.2 Computational Results for the Weighted-Sum Program INTbλ: Maximum Revenue

14.3 Computational Results for the Chebyshev Program INTbλ: Maximum Revenue

14.4 Computational Results for the Weighted-Sum Program INTbλ: Maximum Service Level

14.5 Computational Results for the Chebyshev Program INTbλ: Maximum Service Level

14.6 Computational Results for the Hierarchical Approach

Preface

This book is a unified and systematic presentation of scheduling decision making in supply chains using mixed integer programming (MIP). The recent improvements in modeling, preprocessing, solution algorithms, MIP software, and computer hardware have made it possible to solve large-scale MIP models of scheduling problems, in particular, of scheduling in supply chains. The book demonstrates that MIP, widely used for long- and medium-term planning, can also be efficiently used for the short- and medium-term scheduling and integrated scheduling in customer-driven supply chains, that is, the supply chains in make-to-order discrete manufacturing and assembly environment.

The focus on state-of-the-art MIP modeling and solution approaches means focus on exact optimal or near optimal solutions that can hardly be found when commonly used heuristic algorithms are applied. Furthermore, the proposed MIP modeling and solution approaches allow the reader/user to determine optimal or near optimal schedules using commercially available software for MIP, which makes the decision-making independent of custom-made scheduling software.

It is not necessary to have detailed knowledge of integer programming and scheduling theory in order to go through this book. The knowledge required corresponds to the level of an introductory course in operations research (linear programming, production planning and scheduling, and basic probability for Chapters 9 and 10) for engineering, management, and economics students.

The book is addressed to practitioners and researchers on supply chain planning and scheduling, and to students in management, industrial engineering, operations research, applied mathematics, computer science, and the like at master’s and PhD levels.

TADEUSZ SAWIK

Kraków, PolandMarch 2011

Acknowledgments

The book is based on the results of my research on scheduling in supply chains by mixed integer programming over the last decade. I wish to acknowledge many anonymous reviewers for their comments and suggestions on my submissions to different international journals, including Computers & Operations Research, European Journal of Operational Research, International Journal of Production Economics, International Journal of Production Research, International Transactions in Operational Research, Journal of Electronics Manufacturing, Mathematical and Computer Modelling, and Omega: The International Journal of Management Science.

The material presented in this book is also partially based on the results of different research projects on scheduling in customer-driven supply chains, sponsored by Motorola over the period of 1999 to 2004. The book has benefited from numerous discussions at that time with Andreas Schaller and Tom Tirpak of the Motorola Physical Realization Research Center (formerly Motorola Advanced Technology Center), a corporate R&D lab in Motorola.

This project has been partially supported by the Polish Ministry of Science and Higher Education, research grant No. N N519 576338. Thanks are also due to the AGH University of Science & Technology for its support of research on scheduling and supply chain optimization over the last decade.

Finally, I wish to acknowledge Joanna Marszewska of Jagiellonian University for the cover design of the book.

Introduction

Supply chain management is a rapidly developing field of management science. The purpose of this book is to put forward and present, in a unified and systematic way, practical applications of mixed integer programming modeling and solution approaches to scheduling in customer-driven supply chains.

In a high-tech industry, a typical customer-driven supply chain may consist of a number of part manufacturers at several locations and one or more producers, where parts are supplied by the manufacturers and assembled into finished products, then distributed to customers to meet their demand. In such supply chains, productivity may vary from plant to plant and transportation time and cost are not negligible. Owing to a limited capacity of both the part manufacturers and the producers, the manufacturing and supply schedules for each supplier of parts and the assembly schedules for finished products should be coordinated in an efficient manner to achieve a high customer service level at low cost.

The purpose of supply chain scheduling is to optimize short- to medium-term decisions in supply chains, considering the trade-off between tangible economic objectives such as cost minimization or profit maximization and less tangible objectives such as customer satisfaction or customer service level. In addition to production scheduling, supply chain scheduling considers manufacturing and supply of materials and distribution of finished products, and includes additional decisions connected with functional, spatial, and intertemporal integration and coordination of schedules for these activities.

Short-term supply chain scheduling is typically concerned with the allocation of tasks and resources of a single facility and with detailed sequencing and timing decisions over a short time horizon (e.g., a shift or day) to complete a given number of jobs in such a way that one or more job completion time-related objectives are minimized. A typical single facility considered in a customer-driven supply chain is a single-stage set of parallel machines or a multistage flow shop or job shop with single or parallel machines.

In contrast, medium-term supply chain scheduling (also called planning) deals with the allocation of tasks and resources of one or more interconnected facilities over a longer time horizon (e.g., several shifts, a week, or month) to complete a number of customer orders for finished products in such a way that customer service level is maximized and one or more cost objectives are minimized.