Scheduling in Supply Chains Using Mixed Integer Programming

Tadeusz Sawik

• Publisher: Wiley
• Year: 2011
• Print ISBN: 9780470935736
• eBook ISBN: 9781118029107
• Edition: 1
• Topic: Technology & Engineering
• Subtopic: Industrial Engineering
• Index: Technology & Engineering

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.

Part One

Short-Term Scheduling in Supply Chains

Chapter 1

Scheduling of Flexible Flow Shops.

1.1 INTRODUCTION

This chapter deals with mixed integer programming (MIP) models for scheduling of flow shops, the design in which dedicated machines are arranged in series or in series and parallel, and in which a transportation system imposes a unidirectional flow of parts, with revisiting of machines not allowed. The serial configuration of machines is widely used in many industries, in particular, the serial/parallel configuration with several processing stages in series and one or more parallel machines in each stage, is common in a high-tech industry.

The proposed MIP models cover a wide range of flow shop configurations that can be encountered in modern supply chains. They include flow shops with single or with parallel machines, with infinite, finite, or no in-process buffers, with machines continuously available or machines with one or more intervals of unavailability. The following models are presented:

FI for scheduling flow shops with single machines and infinite in-process buffers

FP for scheduling flow shops with parallel machines and infinite in-process buffers

FIB for scheduling flow shops with single machines and no in-process buffers

FPB for scheduling flow shops with parallel machines and finite in-process buffers

FPBD for scheduling flow shops with parallel machines, finite in-process buffers, and machine down times

All the above models consider makespan minimization as a main scheduling criterion that aims at reaching a high throughput of the flow shop. The models, however, can easily be enhanced for the other common criteria such as total completion time or maximum or total tardiness, if the due dates for some parts are given. The model enhancements are described in Section 1.2.3. The MIP models can also be easily enhanced for scheduling flow shops with nonnegligible transportation times between processing stages (Section 1.2.4) or for scheduling reentrant flow shops (Section 1.2.5), in which a part visits a set of stages more than once.

Finally, for a comparison with the proposed MIP models, two simple, constructive heuristics for scheduling flexible flow shops with finite or with no in-process buffers and with nonzero transportation times, are described in Section 1.3.

1.2 MIXED INTEGER PROGRAMS FOR SCHEDULING FLOW SHOPS

In this section basic MIP formulations are developed for scheduling flexible flow shops of different configuration.

1.2.1 Scheduling Flow Shops with Infinite In-Process Buffers

A regular flow shop consists of m machines in series with unlimited capacity buffers between the machines. In the line n parts of various types are processed (for notation used, see Table 1.1). Each part must be processed without preemption on each machine sequentially. That is, each part must be processed in stage 1 through stage m in that order. The order of processing the parts in every stage is identical and determined by an input sequence in which the parts enter the line, that is, a so-called permutation flow shop is considered (e.g., Baker and Trietsch, 2009).

Table 1.1 Notation: MIP Models for Scheduling Flexible Flow Shops

Indices

i	= processing stage, i ∉ I = {1,…, m}
j	= processor in stage i, j ∉ Ji = {1,…, mi}
k	= part, k ∉ K = {1,…,n}

Input parameters

m	= number of processing stages
mi	= |Ji|—number of parallel processors in stage i
n	= number of parts
Pik	= processing time for part k in stage i
Q	= a large positive constant no...

Table of contents

• Cover
• Half Title Page
• Title Page
• Copyright
• Dedication
• List of Figures
• List of Tables
• Preface
• Acknowledgments
• Introduction
• Part One: Short-Term Scheduling in Supply Chains
• Part Two: Medium-Term Scheduling in Supply Chains
• Part Three: Coordinated Scheduling in Supply Chains
• References
• Index