Scheduling in Supply Chains Using Mixed Integer Programming

By Tadeusz Sawik

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.

• Language: English
• Publisher: Wiley
• Release date: Aug 8, 2011
• ISBN: 9781118029107

Book preview

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.

The typical short-term, operational and medium-term, tactical decisions connected with scheduling in customer-driven supply chains are briefly described below.

1. Short-Term, Operational Decisions

Loading and routing—given a mix of products, the objective of the loading and routing problem is to allocate all tasks and component feeders and/or tools required for completion of each product among the machines with limited work space and/or limited tool magazines, and to select processing routes for a mix of products, so as to balance the machine workloads.

Sequencing and scheduling—detailed sequencing and timing of all tasks for each machine and each individual product so as to maximize the system’s productivity, for example, to minimize the schedule length.

2. Medium-Term, Tactical Decisions

Order acceptance/rejection—decision whether or not to accept a customer request for quotation as a firm order. A request for quotation typically consists of the required quantities of ordered products and the requested delivery dates. A response to the customer request contains the quantity to be fulfilled, the date of delivery, and the price based on revenue management principles, which may involve penalties associated with deviations from the customer-requested quantities and dates.

Due date setting—quoting due date for each accepted order. The quoted due date is either identical with that requested by the customer or a later one if the requested due date cannot be met in view of the actual workload and available capacity. Typically, the due dates setting decisions aim at reaching a high service level (maximum number of orders to be fulfilled by the customer-requested due dates) and can also be based on revenue management principles. The quoted due dates are next considered as deadlines that cannot be violated when the orders are executed.

Supplier selection and order allocation—a single-period or multiperiod allocation of orders for materials among the selected suppliers, respectively with or without timing decisions. The objective is to determine what quantities of various materials to order, from which supplier, and in which periods (in a multiperiod setting) to minimize total ordering, purchasing, defect, and shortage costs.

Customer order scheduling—scheduling of accepted customer orders by the deadlines to achieve some additional objective, such as minimum cost of holding the inventory of finished products completed before the committed delivery dates.

Material supply scheduling—scheduling of material supplies coordinated with the schedules of customer orders to meet demand for materials at minimum cost. The material supply schedules should also be coordinated with the manufacturing schedules for material suppliers to minimize manufacturing, shipment, and inventory holding cost in the supply chain.

The following two main approaches are applied throughout this book for operational and tactical decision making: the integrated (simultaneous) approach, in which all required decisions are made simultaneously using a complex, large monolithic MIP model; and the hierarchical (sequential) approach, in which the required decisions are made successively, using hierarchies of simpler and smaller-sized MIP models.

For the above two approaches, the short- and medium-term decision-making problems can be formulated as below.

1. Short-Term Supply Chain Scheduling

Integrated (simultaneous) approach—given a mix of products, the objective of integrated loading and scheduling is to simultaneously determine the allocation of tasks and component feeders among the machines and a detailed processing schedule for each individual product so as to complete all products and to maximize the system’s productivity, for example, to minimize the schedule length.

Hierarchical (sequential) approach—first, the allocation of tasks and component feeders and/or tools among the machines with limited work space and/or limited tool magazines is determined to balance the machine workloads, and then detailed sequencing and timing of all tasks for each product are found to maximize the system’s productivity, for example, to minimize the schedule length, given the task assignments and fixed or alternative processing routes determined at the top level.

2. Medium-Term Supply Chain Scheduling

Integrated (simultaneous) approach—the coordinated schedules for customer orders, material manufacturing, and material supplies, along with the supplier selection, are determined simultaneously, to achieve a high customer service level (i.e., a minimum number of tardy orders) or a high revenue (e.g., minimum lost revenue due to tardiness or full rejection of orders), at low cost, particularly at minimum cost of holding total supply chain inventory of materials and finished products. The quoted due dates are derived from the completion times of the scheduled orders, whereas the unscheduled orders are considered to be rejected.

Hierarchical (sequential) approach—first, the order acceptance/due date setting decisions are made to select a maximal subset of orders that can be completed by requested due dates, and for the remaining orders delayed due dates are determined to minimize the lost revenue owing to tardiness or rejection of orders. The due dates determined must satisfy capacity constraints and are considered to be deadlines at the order scheduling level. Next, order deadline scheduling is performed to meet all committed due dates and to achieve some additional objective, for example, to minimize the cost of holding finished product inventory of orders completed before the deadlines. Finally, allocation of orders for materials among the suppliers and scheduling of material supplies (and material manufacturing), coordinated with the schedules for customer orders are accomplished to meet demand for the materials in such a way that the total cost of materials manufacturing, supply, and inventory holding is minimized.

Although the integrated approach contributes to the complexity of the underlying mathematical models and the decision-making procedures, it is capable of reaching a coordinated solution and a global optimum for the entire supply chain scheduling problem. The hierarchical approach does not guarantee that the overall optimal solution will be attained. In contrast, the complexity of the hierarchical approach can be significantly reduced; however, it may lead to infeasible solutions obtained at lower decision levels. For example, in the medium-term decision making, no feasible deadline schedule can be found at the customer order scheduling level, if available capacity is overestimated at the due date setting level. Therefore, additional coordinating constraints should be incorporated at different decision levels to avoid the infeasibility issue.

OUTLINE OF THE BOOK

The goal of this book is to enable a reader with a background in MIP approaches to modeling supply chain scheduling problems to apply the knowledge and tools provided to produce state-of-the-art models and solution approaches for tactical and operational problems of real-world supply chains in make-to-order discrete manufacturing environments. To model different scheduling problems, the following three types of decision variables are required:

Binary variables such as assignment variables (e.g., machine assignment, task assignment, due date assignment), time-indexed assignment variables (e.g., order to time period assignment), selection variables (e.g., machine selection, supplier selection, customer order selection), sequencing variables (e.g., precedence variables), machine set-up or start-up variables, etc.

Integer variables such as number of parts, number of machines, number of machine set-ups or start-ups, number of people, etc.

Continuous variables such as timing variables (e.g., completion time or departure time of part, of batch, of customer order), lot sizing variables (e.g., production lot, transportation lot), fractional allocation variables (e.g., allocation of order among suppliers, allocation of order among time periods), cost variables (e.g., tail cost, value-at-risk), etc.

In this book, in addition to MIP models, IP (integer programming) models without continuous variables are presented and, in particular, binary programming models with 0–1 variables only.

The book is divided into three main parts. Part One (Chapters 1 to 4) addresses short-term scheduling and presents various MIP models and some heuristic algorithms for detailed scheduling in flexible assembly lines and general flexible assembly systems. Part One is comprised of these chapters:

Chapter 1, Scheduling of Flexible Flow Shops. This chapter provides the reader with a variety of MIP formulations for scheduling flexible flow shops with single or parallel machines, with infinite, finite, or no in-process buffers and with continuous or limited machine availability. In addition, two fast constructive heuristics are presented for scheduling flexible flow shops with finite or with no in-process buffers.

Chapter 2, Scheduling of Surface Mount Technology Lines. This chapter presents MIP formulations for general or batch scheduling in Surface Mount Technology (SMT) lines with continuous or with limited machine availability. The formulations can be applied for constructing optimal schedules for printed wiring board assembly by using commercially available MIP software, which is illustrated with a set of computational examples modeled after different real-world SMT lines. In addition, a fast improvement heuristic is presented, capable of scheduling different SMT line configurations.

Chapter 3, Balancing and Scheduling of Flexible Assembly Lines. This chapter proposes MIP formulations for simultaneous or sequential balancing and scheduling of flexible assembly lines with infinite or finite in-process buffers. The balancing objective is to determine an allocation of assembly tasks for a mix of products among the assembly stations with limited work space for component feeders and tools so as to balance the station workloads, whereas the scheduling objective is to determine the detailed sequencing and timing of all assembly tasks for each individual product, so as to maximize the line’s productivity. In particular, balancing and scheduling of SMT lines is considered and illustrated with computational examples modeled after real-world assembly lines in electronics manufacturing.

Chapter 4, Loading and Scheduling of Flexible Assembly Systems. This chapter deals with MIP approaches to simultaneous or sequential loading and scheduling of a general flexible assembly system with single or parallel assembly stations, limited work space of assembly stations for component feeders assignment, infinite or finite in-process buffers, and a fixed or alternative assembly routing.

Part Two of the book (Chapters 5 to 10) is concerned with medium-term decision making in supply chains and with supply chain risk management and it presents MIP models and some MIP-based heuristics 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. In particular, Chapters 9 and 10 show that the MIP approach combined with scenario analysis and percentile measures of risk, value-at-risk (VaR), and conditional value-at-risk (CVaR), is capable of solving a hard discrete stochastic optimization problem of selection static or dynamic supply portfolio in the presence of supply chain disruption and delay risks. Part Two has six chapters:

Chapter 5, Customer Order Acceptance and Due Date Setting in Make-to-Order Manufacturing. This chapter considers customer order acceptance/rejection and due date setting decisions combined with order scheduling over a rolling planning horizon in make-to-order discrete manufacturing.

A dual-objective time-indexed MIP formulation is proposed with the solution approach in which the decisions are directly linked with available capacity. The problem objective is to select a maximal subset of orders that can be completed by customer requested dates and to quote delayed due dates for the remaining acceptable orders to minimize the number of delayed orders, the total number of delayed products, or the total revenue as a primary optimality criterion and to minimize the total or maximum delay of orders, as a secondary criterion. A simple critical load index is introduced to quickly identify the system bottleneck and the overloaded periods.

Chapter 6, Aggregate Production Scheduling in Make-to-Order Manufacturing. The purpose of this chapter is to present time-indexed MIP formulations and a lexicographic approach to a dual- or multi-objective aggregate production scheduling in a make-to-order discrete manufacturing environment. The primary scheduling objective is to allocate a set of customer orders with various due dates among planning periods to minimize the number of tardy orders and the secondary objectives are to level the total input and output inventory over a planning horizon, to level the aggregate production, to level the total capacity utilization, or to level the machine assignments, with limited earliness and tardiness for the early and tardy orders, respectively. A close relation between minimizing the total inventory level and the maximum earliness of customer orders is shown and used to simplify the inventory leveling problem. The basic MIP models are strengthened by the addition of some cutting constraints that are derived by relating the demand on required capacity to available capacity for each processing stage and each subset of orders with the same due date.

Chapter 7, Reactive Aggregate Production Scheduling in Make-to-Order Manufacturing. This chapter introduces MIP-based heuristic algorithms for reactive scheduling in a dynamic, make-to-order discrete manufacturing environment. The problem objective is to update a medium-term aggregate production schedule subject to service level and inventory constraints, whenever the customer orders are modified or new orders arrive. Different policies are proposed, from a total rescheduling of all remaining orders through rescheduling only a subset of remaining orders awaiting material supplies to a non-rescheduling of all remaining orders.

Chapter 8, Scheduling of Material Supplies in Make-to-Order Manufacturing. This chapter provides the reader with MIP formulations and enumeration schemes for a cyclic or flexible approach to material ordering and supply scheduling in make-to-order assembly. Computational examples modeled after a real-world make-to-order assembly in the electronics industry illustrate possible applications of the proposed MIP models for a flexible approach and the enumeration schemes for a cyclic approach.

Chapter 9, Selection of Static Supply Portfolio in Supply Chains with Risks. This chapter presents a new portfolio approach for the problem of static (single-period) supplier selection and order allocation in a customer-driven supply chain with operational and/or disruption risks. The selection problem with operational risks is formulated as a single- or multi-objective mixed integer program with the risk of defective or unreliable supplies controlled by the maximum number of delivery patterns (combinations of suppliers’ delivery dates) for which the average defect rate or late delivery rate can be unacceptable. In order to mitigate the impact of disruption risks, the two popular percentile measures of risk, value-at-risk and conditional value-at-risk, are applied. The two different types of disruption scenarios are considered: scenarios with independent local disruptions of each supplier and scenarios with local and global disruptions that may result in disruption of all suppliers simultaneously. The resulting scenario-based optimization problem under uncertainty is formulated as a single- or bi-objective mixed integer program that can be solved using commercially available software for MIP.

Chapter 10, Selection of Dynamic Supply Portfolio in Supply Chains with Risks. The portfolio approach presented in Chapter 9 is enhanced for a multiperiod supplier selection and order allocation in supply chains with disruption and delay risks. The dynamic (multiperiod) selection of supply portfolio in the presence of combined low-probability, high-impact disruption risks and high-probability, low-impact delay risks is modeled using MIP formulations and scenario analysis. The proposed approach is capable of optimizing the dynamic supply portfolio and implicitly of scheduling material supplies, by calculating value-at-risk and minimizing conditional value-at-risk simultaneously. In addition to general scenarios of supplies with on-time, delayed, or disrupted deliveries, the two extreme cases of supplies are considered for which disruptions are combined either with on-time or with longest delay deliveries.

Part Three (Chapters 11 to 14) focuses on coordinated scheduling of manufacturing and supply of parts and assembly of products in supply chains with a single producer and single or multiple suppliers. The intertemporal coordination of medium- and short-term scheduling, as well as the spatial coordination of the producer’s and suppliers’ medium-term schedules, are considered. The two different approaches are applied and compared: the integrated approach with a monolithic large MIP model and a hierarchical approach with a sequence of MIP models. In order to better coordinate the various schedules or decision levels, different coordinating constraints are introduced in the MIP formulations.

Chapter 11, Hierarchical Integration of Medium- and Short-Term Scheduling. This chapter considers an intertemporal coordination of medium-term, aggregate production scheduling and short-term, detailed machine assignment and scheduling in a make-to-order discrete manufacturing environment. A hierarchical decision-making framework with IP and MIP models is proposed and with the objective function that integrates maximization of the customer service level and best utilization of the production resources. Computational examples modeled on a real-world make-to-order flexible assembly system with multicapacity machines in the electronics industry illustrate the hierarchical integration of tactical and operational decision making in a customer-driven supply chain.

Chapter 12, Coordinated Scheduling in Supply Chains with a Single Supplier. This chapter considers coordinated medium-term scheduling of manufacturing and supply of parts and assembly of products in a supply chain with a single supplier and single producer. The supplier manufactures and delivers product-specific parts to the producer where finished products are assembled according to customer orders, and then are delivered to the customers. The overall problem is how to coordinate manufacturing and supply of parts and assembly of products with respect to limited capacities and required customer service level such that the total supply chain inventory holding cost (or maximum total inventory level) and the production line start-up costs at the supplier stage and parts shipment costs are minimized. A monolithic large MIP model is proposed for the overall problem and compared with a hierarchy of interconnected smaller-sized MIP models.

Chapter 13, Coordinated Scheduling in Supply Chains with Assignment of Orders to Suppliers. This chapter looks at coordinated multi-objective scheduling in supply chains with multiple suppliers in which a single supplier of parts is selected for each customer order. The objective functions integrate both the supply chain performance and the customer service level. For the multi-objective scheduling problem a complex, MIP monolithic model is presented and then its decomposition into a hierarchy of much simpler, single-objective MIP models is proposed. The MIP formulations are strengthened by introduction of various coordinating constraints to directly link assembly schedule of the producer and manufacturing and delivery schedules of suppliers. Computational examples modeled by real-world coordinated scheduling in a customer-driven supply chain of high-tech products are reported.

Chapter 14, Coordinated Scheduling in Supply Chains without Assignment of Orders to Suppliers. This chapter looks at the similar coordinated scheduling in supply chains with multiple suppliers, but in a bi-objective setting and without selection of a single part supplier for each customer order. The total demand for parts is allocated among the suppliers so that each customer order can be partially provided with the required parts by different suppliers. In addition to maximum service level, maximum revenue is also considered as an alternative primary objective function, while minimization of the total inventory holding cost is the secondary objective function. An integrated approach with a large MIP model is compared with a hierarchical approach. In contrast to the hierarchical approach presented in Chapter 13, which begins with the combined due date setting and selection of a single parts supplier for each customer order, in this chapter the allocation of demand for parts among suppliers is postponed until the final scheduling of manufacturing and delivery of parts. Computational examples modeled by real-world coordinated scheduling in a customer-driven supply chain of high-tech products are reported.

The proposed models mainly address integrated scheduling decisions at the supply-production stage of a customer-driven supply chain, while decisions for the production-distribution stage are limited to customer order acceptance and due date setting.

The decision-making problems considered in this book are deterministic, with the exception of discrete stochastic optimization problems of single-period or multiperiod supplier selection and order allocation in supply chains with risks, presented in Chapters 9 and 10. In order to tackle the various dynamic disturbances that may occur in supply chains, a rolling planning horizon approach can be applied, to update the decisions made using the proposed deterministic models (e.g., Chapters 5, 6, and 7).

The proposed MIP approaches to operational, tactical, or integrated operational and tactical decision making in customer-driven supply chains are illustrated with many computational examples modeled on real-world supply chain scheduling problems in the high-tech industries. For example, MIP models are presented for balancing and/or scheduling of surface mount technology lines in electronics manufacturing, for scheduling of material supplies in electronics assembly, for the integrated short- and medium-term scheduling in a distribution center for high-tech products, for the coordinated scheduling of manufacturing and supply of custom-made components and assembly of electronic devices in a make-to-order discrete manufacturing environment. In the computational experiments reported throughout the book, an advanced algebraic modeling language AMPL (see Fourer et al., 2003) and the CPLEX solver have been used.

Notation used in this book is consistent within each part of the book, and some consistency of the notation is maintained among different parts. However, the diversity and the complexity of the models presented have made it difficult to develop a uniform notation throughout the book.

The parts and the chapters within each part are arranged in the order recommended for reading. However, the precedence relationship between Parts One and Two is much weaker than that between Parts Two and Three. On the other hand, strictly interconnected Chapters 9 and 10 of Part Two, in which discrete stochastic optimization problems of supply chain risk management are considered, can be read almost independently of the other chapters.

The reader interested in knowing more about scheduling theory is referred to the recent textbook by Baker and Trietsch (2009), which gives an excellent overview of the many aspects of machine scheduling, to an application-oriented book by Pinedo (2005), or to the more advanced books by Bla ewicz et al. (1994, 2007) on computational and complexity aspects of machine scheduling and their applications to computer and manufacturing systems. For a general introduction to integer programming models and techniques, the reader is referred to Wolsey (1998), to the recent application-oriented book by D.-S. Chen et al. (2010), or to the seminal work in the field by Nemhauser and Wolsey (1999). Finally, a number of books cover supply chains in general, and some of these emphasize planning and scheduling, for example, Shapiro (2001), Miller (2002), Voss and Woodruff (2003), and Pochet and Wolsey (2006).

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

Input parameters

Decision variables

Let pik be the processing time on machine i ∉ I of part k ∉ K. For every part k denote by cik its completion time in each stage i as well as its departure time from stage i.

Processing without preemption indicates that part k completed in stage i at time cik had started its processing in that stage at time cik - pik. Each part k completed in stage i at time cik immediately departs that stage for the next stage i + 1, if it is not occupied with another part; otherwise the part is transferred to the buffer with unlimited capacity between stages i and i + 1.

In contrast to the regular flow shop, in which each part requires m operations, each on a different machine, in a general flow shop (Figure 1.1) parts may require fewer than m operations, not necessarily on adjacent machines. Then, the general case can be represented as a regular flow shop in which the processing times on some machines are zero.

Figure 1.1 A general flow shop with single machines.

The production schedule is specified by an input sequence in which the parts enter the line and are processed on each machine as well as by all completion times requited for detailed scheduling of each individual part. The scheduling objective is to determine a permutation of parts such that all the parts are completed in a minimum time, that is, to minimize the makespan Cmax = maxk ∉ K(cmk), where cmk denotes the completion time of part k in the last stage m.

The problem of scheduling a regular flow shop with single machines and infinite in-process buffers is formulated below as a mixed integer program F1.

Minimize

(1.1) equation

subject to

1. Part Completion Constraints:

– each part must be processed on the first machine and successively on all downstream machines,

(1.2) equation

(1.3) equation

2. Part Noninterference Constraints:

– no two parts can be processed simultaneously on the same machine,

3. Maximum Completion Time Constraints:

– the schedule length is determined by the latest completion time of some part on the last machine,

(1.4) equation

(1.5) equation

(1.6) equation

4. Variable Nonnegativity and Integrality Conditions:

(1.7) equation

(1.8) equation

(1.9) equation

The noninterference constraints (1.4) and (1.5) were constructed as follows. For any two parts k and l processed by the same machine i either part k precedes part l, and then processing of l cannot be started until processing of k is completed, or l precedes k, and then k cannot be started until l is completed. As a result, for all i ∉ I and k, l ∉ K: k ≠ l a pair of the following disjunctive constraints must hold

equation

These disjunctive constraints can be replaced with an equivalent pair of conjunctive constraints:

equation

where ykl is the binary sequencing variable defined below

equation

and Q is a large positive constant, not less than the schedule length Cmax.

Note that for all k ≠ l, ykl + ykl = 1 or equivalently ylk = 1 - yki, and hence in the above constraints it is sufficient to define ykl for k < l.

In the next model, a flow shop with parallel machines is considered which consists of m processing stages in series with unlimited capacity buffers between the successive stages and each stage i, (i = 1,…, m) is made up of mi ≥ 1 parallel identical machines (Fig. 1.2).

Figure 1.2 A flow shop with parallel processors.

The flow shop with parallel machines is also known as a hybrid flow shop, flow shop with multiple machines, flexible flow shop, flexible flow line, or multiprocessor flow shop. The problem of scheduling a flow shop with parallel machines may be seen as a combination of two particular types of scheduling problems: the parallel machine scheduling problem and the regular flow shop with single machines scheduling problem. The key decision of the problem of scheduling parallel machines is the assignment of parts to machines, whereas the key decision of scheduling a regular flow shop with single machines is the sequence of parts through the shop. Hence, the main decisions in the operation of the flow shop with parallel machines are to assign and schedule the parts to the machines in each stage, that is, to determine the order in which the parts are to be processed on the different machines of each stage.

In order to determine the assignment of parts to machines in each stage the following decision variables need to be added to the mixed integer programming formulations:

equation

The problem of scheduling a flow shop with parallel machines and infinite in-process buffers is formulated below as a mixed integer program FP.

Minimize (1.1) subject to

1. Part Completion Constraints: (1.2), (1.3)

2. Maximum Completion Time Constraints: (1.6)

3. Machine Assignment Constraints:

– in every stage each part is assigned to exactly one machine,

(1.10) equation

4. Part Noninterference Constraints:

(1.11)

equation

(1.12)

equation

– no two parts assigned to the same machine can be processed simultaneously,

(1.13) equation

5. Variable Nonnegativity and Integrality Conditions: (1.7) to (1.9) and

Part noninterference constraints (1.11) and (1.12) incorporate additional assignment variables xijk and xijl. For a given sequence of parts at most one constraint of (1.11) and (1.12) is active, and only if in stage i both parts k and l are assigned to the same machine j, i.e., only if xijk = xijl 1 (which is always true for stages with a single machine). Otherwise, both (1.11) and (1.12) are inactive. In other words, non-interference constraints (1.11) and (1.12) prevent simultaneous processing of any two parts assigned in some stage to the same machine. However, two parts assigned to different parallel machines in the same stage can be processed in parallel, and then both constraints (1.11) and (1.12) are inactive.

In the above problem setting, all machines within each stage are considered to be identical. Therefore, the processing time of a part on each stage does not depend on the specific machine to which it is assigned. The proposed MIP models are also capable of scheduling flow shops with unrelated parallel machines, in which the processing times of a job in a stage depend on each specific machine within this stage, that is, with the input parameters pik replaced with pijk for each machine j ∉ Ji and some or all stages i ∉ I. This may be due to the differences between the machines themselves, to the fact that a certain type of machine is better suited for processing a particular part, whereas others are not, or because the parts have some special characteristics and can only be assigned to machines that better physically meet them. Also, flexible flow shops with parallel uniform machines in some or all stages (e.g., Kyparisis and Koulamas, 2006) can be considered, where each machine j ∉ Ji has an associated speed vj, that is, when part k is processed in stage i by machine j, it requires pik / vj time units to be completed.

1.2.2 Scheduling Flow Shops with Finite In-Process Buffers

In this section mixed integer programming models for scheduling are presented first for a special case of the flow shop with single machines and no buffers and then for a general case of the flow shop with parallel machines and finite in-process buffers.

A unified modeling approach is adopted with the buffers and machines jointly called processors. The buffers are viewed as special processors with zero processing times but with blocking. As a result the scheduling problem with finite in-process buffers can be converted into one with no buffers but with blocking, see Figure 1.2.

The blocking time of a processor with zero processing time represents part waiting time in the buffer represented by that processor. We assume that each part must be processed in all stages, including the buffer stages. However, zero blocking time in a buffer stage indicates that the corresponding part does not need to wait in the buffer. Let us note that for each buffer stage part completion time is equal to its departure time from the previous stage since the processing time is zero.

A flow shop with single machines and no in-process buffers represents a special type of regular flow shop with no store constraints in which there is only one machine in each stage, and every part visits every machine.

Assume that the flow shop consists of m machines in series with no intermediate buffers between the machines. The system produces n parts of various types and each part must be processed without preemption in each stage 1 through stage m in that order. Let pik be the processing time in stage i of part k. For every part k denote by cik its completion time in each stage i. A part completed on a machine blocks this

machine until the next machine is available and denote by dik its departure time from stage i. This is a new variable that needs to be added to the previous models to account for the blocking scheduling that may occur when the intermediate buffers have limited capacity or there are no buffers at all.

A Gantt chart in Figure 1.3 shows a partial schedule for some part k in stages i and i + 1. Processing without preemption indicates that part k completed in stage i at time cik had started its processing in that stage at time cik - pik. Part k completed in stage i at time cik departs at time dik ≥ cik to the next stage i + 1. If at time cik machine i + 1 is occupied, then machine i is blocked by part k until time dik = ci+1k - pi+1k when part k can start processing on machine i + 1.

Figure 1.3 A partial schedule for part k in a flow shop with no in-process buffers

The problem of scheduling the flow shops with no in-process buffers is formulated below as a mixed integer program F1B.

Minimize (1.1) subject to

1. Part Completion Constraints: (1.2), (1.3)

2. Maximum Completion Time Constraints: (1.6)

3. Part