The Multiple Batch Processing Machine Problem with Stage Specific Incompatible Job Families

Abstract

This contribution introduces the problem of batching and scheduling n jobs in non-permutation flow shops with m ≥ 2 batch processing machines in sequence and stage specific incompatible job families. Batches are build at each stage according to family-specific parameters. This creates a stage-interdependent batching and scheduling problem. We formulate the model by considering different options in terms of release dates, due dates, objective functions as well as setup times and define a corresponding integer linear program.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Introduction

In this contribution we define the multiple batch processing machine problem with stage specific incompatible job families (MBPM_SIF) and test its complexity factor. This problem consist of batching and scheduling multiple products in flow shop environments with multiple stages and intermediate storages in between. In general we understand batching as the task of selecting jobs and building batches out of jobs. Scheduling generates machine specific batch sequences by determining starting and ending times of batch productions. Each stage has one batch processing machine (BPM) with limited capacity. The product orders are represented by jobs during the production phase. All jobs have to be processed on all machines in the same technological order. However, the job sequence is allowed to change between the stages. This is called a non-permutation schedule. For changing the job sequence and for temporary storage we take intermediate storages with infinite capacities into our model consideration. Additionally, we include transport times from machine to storage and vice versa. We assume the options of common or distinct due dates. Furthermore, we introduce stage specific release dates which are the maximum of the availability and realisability of jobs. A job is available in a stage if it has completed all previous stages. A job is realisable if all materials which are required for stage specific job processing are available. The realisability options contain the material availability at time zero as well as randomly-distributed which describes the usage of an arbitrary distribution. There is full knowledge about the production demand and the resulting jobs for a specified time period. The time period can be divided into time slots. The jobs belong to stage specific job families with family-specific processing times. They are incompatible to each other. Such incompatibility results from the production of multiple products and considers realistic production scenarios where products have several product variants. Since product variants have partially the same components or colours jobs for different products can build common batches within a certain stage. This causes a reduction of the variety of different products to a stage specific number of different job families. The feature combination of multiple BPM in sequence and stage specific job families lead to inconsistent batches thus the job constellation of batches only persist for single stages. This is contrary to other batching and scheduling problems where the batch is only build once at the first stage and then endures. Furthermore, the batch building of jobs follows the batch availability model with anticipatory setups, batch sequence-dependent setup-times and a non-preemptive scheduling procedure [compare to (Allahverdi 2008; Potts and Kovalyov 2000)]. Following the batch availability model the jobs have the same starting and end time and become available for subsequent stages at once. Opposing to this in the job availability model jobs of a batch are independent from each other in terms of their completion times. Anticipatory setups specify the knowledge about the next batch in queue for a machine to arrange the setup before its arrival. Batch sequence-dependent setup-times appear if the previous batch on a machine belongs to a different family than the subsequent one. Non-preemptive scheduling exclude the possibility of setting manufacturing priorities for individual jobs. Since the MBPM_SIF induces stage-interdependencies in batching and scheduling, reasonable objective functions are the minimisation of total flow time, total completion time or makespan. Following the notations of Graham et al. (1979), Potts and Kovalyov (2000), we denote our model as Fm/s_ifg, b_i, d_j/∑f_j (Graham et al. 1979; Potts and Kovalyov 2000). For more detailed descriptions about notations and characteristics we recommend (Allahverdi 2008; Potts and Kovalyov 2000).

The research is inspired by a real word scenario. Automakers partially ships their export cars in the so-called Completely-Knocked-Down procedure. Completely-Knocked-Down describes the shipment of cars as assembly sets to save import taxes in the country of destination. Within the preparation phase of the shipment the car components are picked and packed into boxes. To gain economies of scale this process is done by building batches out of boxes with the same content. Following, the boxes come into an intermediate storage. Subsequent the boxes are stuffed into containers with different destinations. The transfer to the above model works as follows: the picking and packing process is the first BPM, the stuffing process the second one. The creation of batches derives from clustering boxes with identical content and stuffing boxes with equal destinations into the same container. Due to this exigences both BPM have their own job families. Also they are limited in space and volume thus they have a maximum batch size.

The objective of this contribution is the formulation of the MBPM_SIF achieving a comprehensive understanding of the problem and thus enabling the development of solution approaches. The article is structures as follows: section Related Work presents a literature review concerning related work. section Problem Statement illustrates the problem and formulates the mathematical model and integer linear program respectively. A summary of the contribution as well as an outlook are presented in section Summary and Outlook.

Related Work

There exist a number of reviews and surveys which precis the state of the art for research concerning batching and scheduling (Allahverdi 2008; Mathirajan and Sivakumar 2006; Potts and Kovalyov 2000; Webster and Baker 1995). We started our literature research on the basis of their categorizations and went over to more specified criteria of our problem such as multiple batch processing machines in sequence and stage specific incompatible job families. These characteristics are the most important ones since they cause discontinues processing and disjunctive sets of jobs for batch formation thus increasing the complexity of batching and scheduling. Furthermore, we only considered batch availability models and offline-algorithm. The focus on offline-algorithm derives from our model which underlies full knowledge of the production demand of a future period. That induces deterministic behaviour.

The combination of multiple BPM in sequence and stage specific job families automatically leads to the appearance of inconsistent batches. There is a very limited number of papers which explicitly consider this characteristic. Ng and Kovalyov (2007) study flow shops with several BPM in sequence and machine-dependent setup-times. They prove for several problems that a permutation schedule is the optimal one (Ng and Kovalyov 2007). However, their demonstration only includes compatible job families. The characteristic of stage specific incompatible job families would impede the feasibility of a permutation schedule. Buscher and Shen (2009) develop a mixed integer programming formulation implying inconsistent batches for a flow shop scheduling problem involving several BPM. Their program is only able to solve small instances and does not consider incompatible job families. Additionally, there are some more approaches on flow shops with multiple BPM in sequence composing consistent batches. For instance Kumar Manjeshwar et al. (2009) as well as Lei and Guo (2011) apply meta-heuristics such as simulated annealing and variable neighbourhood search (Kumar Manjeshwar et al. 2009; Lei and Guo 2011).

Multiple stages and incompatible job families are considered by Fu et al. (2011), Kim et al. (2001), Tajan et al. (2006). Fu et al. (2011) analyse the problem of a two-stage flow shop containing a single BPM following by a discrete processor and a limited buffer in between Fu et al. (2011). Kim et al. (2001) as well as Tajan et al. (2006) study the reverse order which consists of a serial processor feeding a BPM (Yd et al. 2001; Tajan et al. 2006). In all models the incompatible job families are only valid for the batch processing stage. Besides the flow shop focus there are several papers which concentrate on batching and scheduling of single batch processing machines regarding incompatible job families (SBPM_IF). Yao et al. (2012) consider dynamically arriving jobs and analyse different dominance properties. They deduce several lower bounds and propose a basic branch-and-bound algorithm, which they improve to a decomposed branch-and-bound algorithm regarding the dynamic job arrival. The objective is the minimisation of the total completion time (Yao et al. 2012). Koh et al. (2005) study the SBPM_IF in a multi-layer ceramic capacitor production line and propose a number of heuristics as well as hybrid genetic algorithm to solve problems with an extensive number of jobs in reasonable computation time (Koh et al. 2005). A potential transfer of the SBPM_IF approaches to our model is in adapting them onto each stage of our model. However, the stages would be planned separately and without any consideration of interdependencies out of the stage specific scheduling.

Additionally, many researchers analyse the batching and scheduling problems of single stages including identical or non-identical parallel batch processing machines with incompatible job families (PBPM_IF).Their research is mostly motivated by semiconductor wafer fabrication. Jula and Leachman (2010) propose exact and heuristic algorithms for the PBPM_IF. Their model also includes feeding and removing apparatus (Jula and Leachman 2010). Chiang and Cheng (2010) develop a memetic algorithm for minimizing total weighted tardiness in PBPM_IF regarding dynamic job arrival and incompatible job families. Their algorithm plans the batch formation and batch sequence simultaneously (Chiang and Cheng 2010). Since the papers of this category mainly focus on the usage of common resources and do not regard scheduling dependencies across stages we do not consider more approaches and refer to Mathirajan and Sivakumar (2006).

Summarising the results of our literature research we notice that no analysed model or approach combines the characteristics of multiple batch processing machines in sequence and stage specific incompatible job families. However, the illustrated research presents related and interesting work and deals with certain elements of our problem. Hence, they may support the following problem formulation.

Problem Statement

In general, batching and scheduling problems consist of two fundamental decision for each BPM. The first one concerns the batch formation, the second one contains the batch sequencing. Regarding our model we need to be aware that both problems are related to each other due to the characteristics such as incompatible job families and BPM capacities. Naturally the batch formation precedes. However, it influences the completion time of a batch by arranging its batch size and thus determining the availability of the containing jobs for subsequent BPM. Since the following BPM has another job families than its predecessor the batch cannot automatically proceed as a whole, it could contain incompatible families for the BPM. This effects a necessary re-formation of the batches between the stages. Smaller batch sizes could reduce this problem, but they are causing more setup-times by an increased changing rate of batch families and decrease the efficiency of the BPM. For permuting the job sequence and composing new batch formations there are storages with unlimited capacities located between the BPM. This ensures that BPM never block. Due to the option of distinct due dates and the re-formation of batches we notice that jobs of the same batch may vary in their stage specific release dates and deadlines. In addition, the planning problem could be more complex by introducing production time slots. They have limited time capacities and batches are mostly not allowed to split across them. They need to be completed within one time slot. However, the option of different time slots are not considered in the following notation and problem formulation.

Mathematical Problem Formulation

Following, we present the notation and underlying assumptions of the integer linear program of the MBPM_SIF. We use the following notation:

• Subscripts

k = 1,…,m:

Machine index

j, i, c = 1,…,n:

Job index

s = 1,…,x:

Storage index

a _k  = 1,…,g _k :

Family index on machine k

• Parameters

P _k,j :

Processing time of job j on machine k

Z _j :

Due date of job j

u _k,j :

Setup time for job j on machine k (equal for all family members)

SMIN _k , SMAX _k :

Minimum and maximum batch size at machine k

T _k,s , T’ _s,k :

Transport time for batches from k to s and vice versa

EoS _k,j :

Economies of scale for job j if its batch has more than one job

bigM :

Big integer number

• Binary variables

$\delta_{k,j,i}$ :

1 if job j is scheduled before job i on machine k

θ _k,j,i :

1 if job j is direct predecessor of job i on machine k

$\gamma_{k,j,i}$ :

1 if job j and i belongs to the same family on machine k

$\pi_{k,j}$ :

1 if job j has a directly preceding job on machine k which belongs to the same family

B _k,j,i :

1 if job j and job i belongs to the same batch on machine k

$\phi_{k,j,i,c}$ :

1 if job c is scheduled between j and i on machine k

• Integer variables

C _j :

Completion time of job j

f _j :

Flow time of job j

C _max :

Makespan

r _k,j , r′ _k,j :

Start and completion time of job j on machine k

v _k,j :

Shortfall below SMIN _k of the batch containing job j

D _k,j :

Deadline of job j on machine k

A _k,j :

Realisability date of job j on machine k

R _k,j :

Release date of job j on machine k

There are several assumptions. Besides the intermediate storages additional storages are located before the first and after the last batch processor. Hence, the flow shop has x = m + 1 storages. All jobs have to pass all storages. Transport times are from machines to storages and vice versa and count for the whole batch. The production planning is far ahead of the end of the production period thus we assume an infinite time horizon. The following integer linear program focuses mainly on the minimisation of the total flow time. Thereby it uses batch sequence-dependent setups. Both can be easily substituted by other objectives and setup approaches.

• Problem Formulation

Objective function

$$ min\;v_{k,j} + \left\{ {\begin{array}{*{20}l} {\sum\nolimits_{j = 1}^{n} {f_{j} } } & {{\text{if}}\;{\text{objective}}\;{\text{is}}\;{\text{total}}\;{\text{flow}}\;{\text{time}}} \\ {\sum\nolimits_{j = 1}^{n} {C_{j} } } & {{\text{if}}\;{\text{objective}}\;{\text{is}}\;{\text{total}}\;{\text{completion}}\;{\text{time}}} \\ {C_{max} } & {{\text{if}}\;{\text{objective}}\;{\text{is}}\;{\text{makespan}}} \\ \end{array} } \right. $$

(1)

Environmental constraints and definition

$$ f \ge \sum\limits_{k = 1}^{m} {\sum\limits_{j = 1}^{n} {v_{k,j} } + \sum\limits_{j = 1}^{n} {(Z_{j} - r_{1,j} )} } $$

(2)

$$ r_{k,j}^{\prime } \ge r_{k,j} + (1 - \pi_{k,j} ) \cdot u_{k,j} + P_{k,j} \cdot \sum\limits_{i = 1}^{\text{n}} {B_{k,j,i} - EoS_{k,j} \cdot ( - 1 + \sum\limits_{i = 1}^{n} {B_{k,j,i} } )\quad \forall k,j} $$

(3)

$$ \sum\limits_{j = 1}^{n} {{{\uptheta}}_{k,j,i} \cdot \gamma^{\prime}_{k,j,i}- \pi_{k,i} \cdot bigM \le 0\quad \forall k,i}$$

(4)

$$ \sum\limits_{j = 1}^{n} {{{\uptheta}}_{k,j,i} \cdot \gamma^{\prime}_{k,j,i} + (1 - \pi_{k,i} ) \cdot bigM \ge 1\quad \forall i} $$

(5)

$$ r_{k,j} \ge r_{k - 1,j}^{\prime } + T_{k - 1,s} + T^{\prime}_{s,k} \quad \forall k > 1,j,s $$

(6)

$$ r_{m,j}^{\prime } + T_{m,x} \le Z_{j} \quad \forall j $$

(7)

Machine constraints

$$ \sum\limits_{j = 1}^{n} {B_{k,j,i} \le\; SMAX_{k} \quad \forall k,i} $$

(8)

$$ v_{k,j} + \sum\limits_{j = 1}^{n} {B_{k,j,.i} \ge\; SMIN_{k} \quad \forall k,i,v_{k,j} \le 1} $$

(9)

$$ r_{k,j} \ge r_{k,i}^{\prime } - bigM \cdot (\delta_{k,j,i} + B_{k,j,i} )\quad \forall k,j,i,j \ne 1 $$

(10)

$$ r_{k,i} \ge r_{k,i} - bigM \cdot (1 - \delta_{k,j,i} + B_{k,j,i} )\quad \forall k,j,i,j \ne 1 $$

(11)

$$ \delta_{k,j,i} + \delta_{k,i,j} + B_{k,j,i} \le 1\quad \forall k,j,i $$

(12)

$$ \delta_{k,j,i} + \delta_{k,j,c} + \delta_{k,c,i} - \phi_{k,j,i,c} \cdot bigM \le 2\quad \forall k,j,i,c $$

(13)

$$ \delta_{k,j,i} + \delta_{k,j,c} + \delta_{k,c,i} + (1 - \phi_{k,j,i,c} ) \cdot bigM \ge 3\quad \forall k,j,i,c $$

(14)

$$ \sum\limits_{c = 1}^{n} {\phi_{k,j,i,c} - (1 - \delta_{k,j,i} + \theta_{k,j,i} ) \cdot bigM \ge 1\quad \forall k,j,i,j \ne i} $$

(15)

$$ \sum\limits_{c = 1}^{n} {\phi_{k,j,i,c} - (2 - \delta_{k,j,i} - \theta_{k,j,i} ) \cdot bigM \le 0\quad \forall k,j,i,j \ne i} $$

(16)

$$ \delta_{k,j,i} \ge \theta_{k,j,i} \quad \forall k,j,i $$

(17)

Batch constraints

$$ r_{k,j} \ge r_{k,i} + 1 - (1 - \delta_{k,j,i} ) - bigM\quad \forall k,j,i $$

(18)

$$ r_{k,j} \ge r_{k,j} - \delta_{k,i,j} \cdot bigM\quad \forall k,j,i $$

(19)

$$ B_{k,j,i} \le \gamma^{\prime}_{k,j,i} \quad \forall k,j,i $$

(20)

$$ B_{k,j,j} \ge 1\quad \forall k,j $$

(21)

$$ \delta_{k,j,i} + \delta_{k,i,j} + B_{k,j,i} \cdot bigM \ge 1\quad \forall k,j,i $$

(22)

The objective function (1) includes the options of minimising the total flow time, the total completion time or the makespan. Additionally, there are also the conceivable options of minimising the mean flow time n ⁻¹ ∑ f _j or mean completion time n ⁻¹ ∑C _j . Since they are equal to total flow time and total completion time we do not formulate them explicitly. The choice of the objective criterion depends on the motivation for analysing the MBPM_SIF. While the usage of the total flow time criterion allows a more intensive consideration of storages, the total completion time criterion focuses on the BPM. As the Eq. (2) describes, the above formulation focuses on the total flow time. However, the exclusively pursuance of this objectives would partially in contrast to the fundamental idea of batch processing which is driven by economic efficiency. Supposing the abandonment or insignificance of setup-times decision-makers would prefer batches of size one since they do not cause waiting times in storages until other jobs of the same job family are available. Hence, we introduce a weak constraint (9) for the minimal batch size of a BPM. This weak constraint is regarded in the objective function by the term of v _k,j which defines the shortfall of the minimal batch sizes. It is restricted to allow a shortfall of at most 1. In contrary to Eq. (9) constraint (8) refers to the maximum number of jobs within a batch. Due to the physical bounded space it is constructed as a hard restriction which needs to be regarded strictly. The batch sequence-dependent setup events are determined by the constraints (4) and (5). These constraints work as an either-or-option. They analyse if one of the directly preceding jobs of j belongs to the same family as j does. The term (3) describes the completion time of a job depending on its production start on the machine, a potentially setup as well as the duration of the corresponding batch. The batch duration derives from the sum of the jobs processing times on machine k as well as on the economies of scale. This effect allegorises the savings of time which occur by the aggregation of material provisions, identical working procedures, learning effects etc. We advert that this formulation of setups only specifies when a setup precedes a batch, it does not quantify their duration. These could be constant for all families, family-dependent, machine-dependent or both. Constraint (6) defines the technological order of machines. All jobs needs to pass all machines and all storages. Equation (7) ensures that all jobs are in the last storage until their due dates. The constraints (10) and (11) identify the order of jobs and avoid overlapping of batches. They are also formulated as a either-or-option. In the case that job j is scheduled at any time before job i δ _k,j,i is 1. If the jobs build a common batch or if j is scheduled after i δ _k,j,i is 0. Equation (12) avoids bidirectional hierarchies and ensures that two jobs either have one hierarchy proportion or that they constitute a common batch. The complementary constraint to this is (22). For the case that there is no hierarchy proportion it reasons that the jobs build a common batch. The constraints (13 and 14) determine whether a job c is between job j and job i. This serves as a basis for the Eqs. (15 and 16). They count the number of jobs between job j and job i. If the sum of the intermediate jobs is 0 job j is a direct predecessor of i. In this case the sequence variable θ _k,j,i is set to 1. Constraint (17) defines that the sequence variable θ _k,j,i only can be set to 1 if the order variable δ _k,j,i also is 1. That means that job j can only be a predecessor of job i if they have an equal hierarchical order. The Eqs. (18 and 19) defines the same starting time for jobs of the same batch. The constraint (20) makes sure that jobs only can constitute a batch if they belong to the same job family on machine k. Equation (21) completes the matrix of B _k,j,i and ensures that the belongings of two jobs to the same batch are bidirectional.

Analysing the problem size and complexity of the integer linear program we applied the pre-solver of GUROBI (Bixby et al. 2012) The scenario consist of m = 2 BPM, random job family processing times P _k,j between 20 and 60 min, EoS is 15 % of the job′s process duration, the due dates Z _j out of an interval of 100 min, family-specific setup times u _k,j of 50 % of a full sized batch of the specific family and transport times T _k,s as well as T′ _s,k of 5 min. The other parameters SMIN _k , SMAX _k , g_k as well as the numbers of integer variables, binary variables and nonzeros after pre-solving are described for exemplary cases in Table 1.

Table 1 Exemplary problem sizes

Extending the above described model we further present the mathematical formulations of stage specific release dates and deadlines. They are necessary for the development of heuristically solution approaches solving the MBPM_SIF.

$$ R_{{k,j}} = \left\{ {\begin{array}{*{20}l} {{\text{max}}\left\{ {{\text{A}}_{{k,j}} {\text{,r}}_{{k - 1,j}}^{\prime } {\text{ + T}}_{{k - 1,s}} + T_{{s,k}}^{\prime } } \right\}} & {{\text{if}}\;k > 1} \\ {A_{{j,k}} } & {{\text{else}}} \\ \end{array} } \right.\quad \forall k,s = k$$

(23)

$$ D_{k,j} = \left\{ {\begin{array}{*{20}c} {{\text{r}}_{k + 1,j} {\text{ + T}}_{s,k + 1}^{\prime } - T_{s,k} } & {{\text{if}}\;k < \;m} \\ {Z_{j} - T_{k,s} } & {\text{else}} \\ \end{array} } \right.\quad \forall k,s = k $$

(24)

According to Eq. (23) the release date of job j on machine k + 1 results out of the maximum of its realisability date and its availability date. The realisability date corresponds to the provision of required material in the specific stage. The job availability date results from the completion of its batch on the previous machine k − 1 and the transport times for the batch from machine k − 1 to storage s = k to machine k. If k = 1 the availability of the job only depends on its realisability. The deadline D _j,k of a job j for machine k results by calculating the reverse order in (24). If k = m the job′s deadline derives from its due date instead of its starting time on the following machine. This calculations are equal if the MBPM_SIF contains common or distinct due dates or if the realisability dates are chosen as time zero or distributed. If the focus of analysing the MBPM_SIF excludes storages the transport times can be set to zero.

Problem Complexity

Since we allow a high variety of combinations in terms of due dates, deadlines, objective function etc. we only address exemplary cases for providing different perspectives on the complexity of MBPM_SIF. First we want to consider the case that we have different time slots with equal time capacity. The batches have non-identical durations. If we pursuit the minimisation of makespan C_max it is advantageous to realise a maximum usage of the time slots, i. e. no idle times of machines. This problem layout is equal to the one dimensional bin packing problem where we have bins of limited capacity and boxes of non-identical sizes. The bin packing problem is known as NP-hard (Garey et al. 1976). However, this reduction only regards the scheduling problem and does not work if we have only one time period with infinite time capacity. For this case Glass et al. (2001) proof for a flow shop of m = 2, g _k  = 1 for all k, inconsistent batches and the objective of minimising the makespan that it is NP-hard in the strong sense. But they do not explicitly regard incompatible families. This is done by Webster and Baker (1995) for SBPM_IF and different objectives. According to Uzsoy (1994) and for the objective of minimising total flow time they show that the problem is NP-hard (Webster and Baker 1995). The case of distinct release dates is considered by (Yuan et al. 2006). They proof that the SBPM_IF is strongly NP-hard even for two distinct release dates and also if the processing times of the jobs are equal and the job families have identical setup-times. The MBPM_SIF has distinct release dates in each stage of the flow shop. Garey and Johnson (1990 ) proved that finding the minimum mean flow time schedule in a flowshop of m ≥ 2 machines is NP-complete (Garey et al. 1976). If we take the job constellation for batches as a given, the challenge of MBPM_SIF only consist of finding the best schedule. Due to the presented results we assume that the MBPM_SIF is also NP-complete. This degree of complexity is not effected by regarding or omitting distinct due dates or varying realisability dates. Different release dates in a stage results from the feature combination of multiple stages and stage specific incompatible job families. Therefore, all presented variants of the MBPM_SIF are NP-hard.

Summary and Outlook

This contribution introduces and formulates the MBPM_SIF as a logical extension of SBPM_IF and PBPM_IF. The mathematical formulation describes a general model which allows flexibility in terms of the objective function, release dates, due dates, setup-times and storage consideration. Using a solver for model consolidation we illustrate the problem complexity for small scale test cases. According to the results of other researches we classify the MBPM_SIF as NP-hard.

Further research should be done to find feasible solution approaches for the MBPM_SIF. Due to the hardness of the problem exact algorithms or MILP solver only can solve small instances. They could contribute to the understanding of the problem by determining the significance of single elements for the problem complexity. However, feasible solutions for more extensive instances only can be provided by heuristics. The development of heuristic needs to be made for specified characteristics of the MBPM_SIF since this ensures a higher quality of the computed solution. Further one, such a solution could be serve as a basis method for improvement by developing and applying meta-heuristics [compare to Kumar Manjeshwar et al. (2009); Lei and Guo (2011)]. The MBPM_SIF does not need restricted to the described options. Many more modifications and extensions are thinkable as long they do not change the characteristics of multiple stages and stage specific incompatible job families.