Abstract
Typical simultaneous lotsizing and scheduling models consider the limited capacity of the production system by respecting a maximum time the respective machines or production lines can be available. Further limitations of the production quantities can arise by the scarce availability of, e.g., setup tools, setup operators or raw materials which thus cannot be neglected in optimization models. In the literature on simultaneous lotsizing and scheduling, these production factors are called “secondary resources”. This paper provides a structured overview of the literature on simultaneous lotsizing and scheduling involving secondary resources. The proposed classification yields for the first time a unified view of scarce production factors. The insights about different types of secondary resources help to develop a new model formulation generalizing and extending the currently used approaches that are specific for some settings. Some illustrative examples demonstrate the functional principle and flexibility of this new formulation which can thus be used for a wide range of applications.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
As it has been shown by the literature review of Copil et al. (2017), there has been a great research interest in simultaneous lotsizing and scheduling over the last decades. The formulated models typically consider one or just a few production stages. Each production stage may consist of one or more parallel machines (often aggregated to production flow lines if the sequence of machines is fixed and identical for all products) with scarce capacities. Furthermore, setup times and costs, which may be sequence-dependent, occur due to changeovers from one product to another. Product-specific demand is given per period and varies dynamically over time. If large lotsizes are built, the products have to be stored, which causes inventory holding costs. Many of the current model formulations are directly motivated by practical applications. Due to improvements in modeling knowledge, solution techniques and computing power, it is now possible to represent industrial challenges in a more detailed manner.
Nevertheless, most of these simultaneous lotsizing and scheduling models consider the production capacity of these machines or production lines as the only limiting factor. In other words, fulfilling the given demand of the products in a cost minimal way is solely limited by the available production capacities of the machines or production lines. In the literature on production processes, these machines or production lines are called “resources”. These resources are utilized in a process to transform an “input” (e.g., raw material), which normally is available in an unlimited manner in short-term planning, to an “output” (e.g., final product) which normally has a higher value compared to the input (see, e.g., Anupindi et al. 2014, Chapter2). Just a few of the simultaneous lotsizing and scheduling models also take further resources which limit the production quantity of the products into account. In the literature on simultaneous lotsizing and scheduling, such further resources with limited capacities are called “secondary resources” (SRs; see Copil et al. 2017). Recognize, the term resource in secondary resource is not used in the classical way like it is defined above. It simply names something which additionally limits the production quantities of the products (this also implies that it is only named a secondary resource if it is scarce). This limitation can be caused in several ways as illustrated in the following examples. The first two refer to a first type of secondary resources called “cumulative (secondary) resources”.
Example 1
Assume that two production lines exist. Production line 1 is capable of producing 20 units of product 1 in period 1, and production line 2 is capable of producing 20 units of product 2 in the same period. (Assume that these capacities will be totally utilized in an optimal production plan.) As mentioned above, normally, in short-term planning raw materials are available in an unlimited manner and thus neglected in planning models. Nevertheless, it might happen that due to, e.g., natural disasters, the necessary raw material to produce product 1 is limited in a way that only 15 units of product 1 can be produced in period 1. In this case, the raw material becomes a secondary resource and it is necessary to introduce an additional capacity restriction which respects this fact.
Example 2
Alternatively let us assume that during the production of product 1 and 2 a byproduct (e.g., a contaminated liquid) occurs. Subsequently, this contaminated liquid has to be filtered using a machine. Assume that if 20 units of product 1 and 20 units of product 2 are produced in period 1, 40 L of contaminated liquid occurs. However, the machine which filters the contaminated liquid is only capable of cleaning 30 L of liquid per period. Thus, the overall production quantity of product 1 and product 2 is additionally limited by this filtering machine in period 1.
Two differences of Example 2 to Example 1 attract attention. First, the output of the primary resources’ production processes is limited and not their input. Secondly, although the limited production capacity of the filtering machine is the original bottleneck, this second stage of production needs not to be modeled in detail. It is sufficient to simplify the model by limiting the cumulated output of contaminated liquid of the first stage to 30 L instead of also modeling all lotsizing and scheduling decisions of the second stage of production. This is the typical motivation for favoring a single-stage model with SRs over a two-stage simultaneous lotsizing and scheduling model. Note that both examples have in common that the total—i.e., “cumulated”—input or output of the primary resources (production lines 1 and 2) is the secondary scarce resource. Thus, this type of input-/output-related SRs will in the following be called “cumulative (secondary) resources”.
Another type of secondary resources will be called “disjunctive (secondary) resources”. Again two examples shall ease understanding.
Example 3
The example above is continued. Assume that a certain tool is necessary for the production of product 1 and 2 and that only a single piece is available due to investment restrictions. Thus, it can be seen as scarce. Moreover, the tool can only be used on one line at the same time, meaning that, if it used on line 1, the production quantity of line 2 is limited to zero. The term disjunctive resource is based on the characteristic that there is a disjunction (exclusive or) in the use of such a resource. It can be either used on line 1 or on line 2 at any point in time.
Example 4
Assume products 1 and 2 are beverages which are produced on a single production line. This production line is directly connected to a single bottling line on a second stage of production. Bottling itself is slower than production, but sequence-dependent setup times of bottling are sometimes shorter than those of liquid production. To avoid a detailed modeling of the first stage, only a single-stage lotsizing and scheduling model of the second stage is formulated where a “virtual setup tool” (secondary resource) is introduced which occupies the bottling line for the maximum of the production setup time and bottling setup time. Thus, either the production setup time or the bottling setup time is binding (disjunctive SR), depending on which is longer.
Therefore, again Example 4 uses an SR to avoid a more complex model with an additional production stage, whereas Example 3 models an actually single-stage situation in a more realistic manner. However, both examples have in common that the disjunctive SR occupies a primary resource for some time—no matter whether this is during a production or during a setup process. Thus, whereas cumulative SRs concern the inputs or outputs of primary resources, disjunctive SRs concern the primary resources themselves. Note that the same disjunctive SR can be used several times during the planning horizon. For example, the single tool of Example 3 can be used in period 1 and in period 2 as well. In this sense its capacity is renewable. In contrast, the same, single unit of a cumulative SR can only once be input to or output from a production process. Then it has either been transformed into a successor product or it leaves the scope of the model. In this sense it is non-renewable. However, several units of such a cumulative SR can become available anew, in each period of the planning horizon. This distinguishes a non-renewable resource of a simultaneous lotsizing and scheduling model from a non-renewable resource of a model for the resource-constrained project scheduling problem (RCPSP) whose planning horizon usually is not subdivided into discrete planning periods with time-varying demand and time-varying capacities. Nevertheless, the terms “renewable,” “non-renewable,” “cumulative,” and “disjunctive” used here as far as possible correspond with the ones known from the RCPSP literature, where a disjunctive resource is sometimes also called a dedicated resource [see Hartmann and Briskorn (2010, Sects. 4.3 and 4.5)]. All in all, it is important to recognize that if secondary resources were completely neglected in the planning process, resulting plans might become infeasible for real-world industrial applications. However, it is not necessary to model secondary resources in every detail.
This paper provides a structured literature overview on simultaneous lotsizing and scheduling models which take secondary resources into account. The different types of resources that appear in different industrial settings are clustered using a unified classification. This overview will illustrate that—with respect to the secondary resources—the models of the literature are very specialized and suffer from lack of generality. Thus, this paper further introduces a general model formulation which is capable of handling all types of secondary resources addressed in the literature until now. Additionally, it also incorporates some functionalities which have not been represented in the literature so far, but seem reasonable for production planning as, for example, the splitting of setups into dismounting and mounting operations. Such modeling features do allow more flexible and thus more realistic production plans.
The presented model is based on the general lotsizing and scheduling problem (GLSP) of Fleischmann and Meyr (1997) and its single-stage extension for parallel production lines (GLSPPL) by Meyr (2002). It relies on a discrete time grid consisting of so-called macroperiods. In a macroperiod multiple setups are possible. Nevertheless, for a detailed representation of the product sequence the model also uses “microperiods” with flexible length. In a microperiod at most one setup is possible. We use this microperiod structure to assure that, for example, a setup operator can be scheduled on at most a single production line at the same point in time. Since the GLSP is based on macroperiods it is called a “large-bucket” model.
The literature review will be given in the following section. It closes with a short discussion of the presented models and motivates the need for a more general and extended formulation. In Sect. 3, we modify the GLSPPL in a way that a common, but flexible microperiod time grid is simultaneously used for all parallel lines. This builds the basis to synchronize the usage of different types of secondary resources in Sect. 4. Section 5 shows how additional features that may become relevant in real-world applications can be incorporated into the new model. Numerical examples, which demonstrate the flexibility and broad applicability of the new model, are presented in Sect. 6. Finally, Sect. 7 provides a brief summary and identifies opportunities for future research.
2 Literature review
In the following, we review simultaneous lotsizing and scheduling models which incorporate scarce SRs. We concentrate on characteristics that are important in the SR context. Additional, more general information about the presented models can be found in Copil et al. (2017). The two, probably most important characteristics are the “shareability” and “substitutability” of SRs. Shareability concerns the question whether a secondary resource can be used on only a single or on several production lines in parallel (i.e., at the same point in time) and whether it can only be used once or several times. As already explained in Sect. 1 we denote an SR as
-
“disjunctive” if it serves (e.g., a setup operator) or occupies (e.g., a setup tool) a primary resource such as a production line for a certain amount of time. It can only serve/occupy a single primary resource at a single point in time. The same disjunctive SR can be used several times consecutively, even on different primary resources.
-
“cumulative” if it is input to (e.g., in case of raw materials) or output from (e.g., in case of (by-)products) one or several primary resources. The SR’s relevant goods flow can—but not necessarily needs to—be a cumulated quantity, originating from several sources or going to several destinations simultaneously (e.g., in case of fluids). The same basic unit of a cumulative SR can only be used once during the planning horizon.
The quantity available of the same type of SR in a certain period of planning may be scarce so that the SR can become a bottleneck.
In order to explain the term substitutability, it is necessary to discuss the term “process” in some more detail. Let us define a process as an operation which takes place on a production line in a certain period. We will distinguish between the three processes changeover from product i to j, conservation of the setup state of product j (standby) and production of product j. Changeover from product i to j means that product j is set up in a certain period s on a production line and that this production line has been set up for product i in a previous period and is still prepared to produce this product in period \(s-1\). If a machine has been set up for a product, two possible processes can take place afterward. Of course, it is possible to produce product j. On the other hand, it is also possible to simply conserve the setup state of product j without production. That is, idle periods without production might exist, but an additional setup after these idle periods is not necessary if the same product j is produced again. Substitutability distinguishes whether only a single type of SR can be used for a certain changeover, standby or production process (this case is denoted as “without substitutes”) or whether several different types of SRs do exist which could alternatively be applied (“with substitutes”). High- and low-skilled workers can serve as an example: a complex changeover process might only be executed properly by high-skilled operators (i.e., low-skilled operators cannot serve as substitutes), whereas simple changeovers could be executed by both types of workers alternatively.
The review is structured on the basis of these resource characteristics into the three subsections “disjunctive resources without substitutes” (Sect. 2.1), “disjunctive resources with substitutes” (Sect. 2.2) and “cumulative resources without substitutes” (Sect. 2.3). We are not aware of work concerning the remaining combination in the context of simultaneous lotsizing and scheduling although industrial applications comprising cumulative resources with substitutes do certainly exist. For example, Balakrishnan and Geunes (2000) and Geunes (2003) consider requirements planning models to choose a cost minimal option out of several possible substitute components. Finally, Table 2 of Sect. 2.4 gives an overview. It further classifies the work on SRs in simultaneous lotsizing and scheduling by summarizing additional SR-relevant characteristics that have been identified and discussed in the preceding sections. This helps us to derive shortcomings of the current state of the art and to motivate the new model to be introduced in Sect. 4.
2.1 Disjunctive resources without substitutes
This subsection examines models which incorporate disjunctive SRs such as setup operators, which perform the changeovers, or cutting tools, which are necessary for production. These disjunctive resources can only be assigned to one production line at the same point in time. These resources are used but not consumed. Additionally, only resources without substitutes are considered. That means, all publications presented in this subsection assume that for each process (changeover from product i to j, conservation of the setup state of product j (standby) and production of product j) of the production line it is explicitly known which resources are necessary. For example, there is no decision on which setup operator (e.g., operator A or B with different skill levels) performs a changeover from product i to j.
Lasdon and Terjung (1971) present a discrete lotsizing and scheduling problem (DLSP)Footnote 1 formulation for a tire manufacturer. The main characteristic of the DLSP is the all-or-nothing assumption, i.e., a product is produced for a complete period or there is no production at all. The problem of the tire manufacturer comprises parallel, identical machines. To produce product j it is necessary that a machine is set up for this product and that an additional die (secondary resource) is available. Since the DLSP is a small-bucket model, the synchronization of the resources (assuring that there is no overlapping use of the same SR on two or more different lines) is achieved using the given time structure, i.e., the resource is assigned for the complete period to a certain line. In a large-bucket model this approach is often too restrictive since the resource’s usage on another line would be blocked for quite a long time. In addition, the model is extended to consider setup operators and other equipment which is needed to perform a changeover. Eppen and Martin (1987) propose a new solution approach for the basic model (without setup resources) of Lasdon and Terjung (1971).
A proportional lotsizing and scheduling problem (PLSP, see Drexl and Haase 1995) formulation which considers secondary resources is presented by Kimms and Drexl (1998, pp. 89–90). The PLSP uses continuous lotsizes and provides the possibility to produce at most two different products per microperiod on condition that one of the products has already been set up in a previous period. The presented multistage model formulation neglects setup times and assumes that each product is assigned to exactly one line. Nevertheless, different products can be assigned to the same production line. Each product requires multiple resources which all must be in the correct setup state. Synchronization of the resources is performed using the microperiod time grid.
Another example from a tire manufacturer is given by Jans and Degraeve (2004). The model is formulated as a DLSP with setup times. Tires are produced using different heaters. There can be multiple identical replicates of a heater type. Additionally, a mold is always necessary to produce a tire. For each possible tire–heater combination a limited number of molds are available. Due to short microperiods the molds can be assigned to active tire–heater combinations for complete periods.
A problem from the injection molding sector is considered by Dastidar and Nagi (2005). The authors use a continuous setup lotsizing problem (CSLP) formulation (Karmarkar and Schrage 1985), i.e., continuous lotsizes are possible and the number of products is limited to at most one per microperiod. Different products are produced on multiple parallel machines. For each product–machine combination a bundle of different SRs (e.g., grinders, driers) is necessary. There can be multiple replicates of the same resource. Nevertheless, at most one of these replicates is required to produce a product. Again, resources are assigned to the machines for complete periods. The model respects setup times. The resources are already necessary during the setups of the products.
Tempelmeier and Buschkühl (2008) consider a common setup resource in their PLSP formulation. That is, only one setup operator is responsible for all setups. Since each product is dedicated to just one line, the setup operator is the only reason for a simultaneous planning of all lines. Continuous variables are used to record the beginning of a setup on a machine in each microperiod. Binary variables document the machine-visiting sequence of the setup operator. The setup operator has a given time budget per period which can be less than or equal to the production capacity in this period. Constraints assure that the starting time of each setup is later than the ending time of the preceding setup on the previous line. Tempelmeier and Copil (2016)Footnote 2 tackle the same problem but using a CLSD (capacitated lotsizing problem with sequence-dependent setups) formulation. The CLSD was presented first by Haase (1996). It is a large-bucket model and uses a numbering of the products within a macroperiod—similar to a tour of a Traveling Salesman Problem. Tempelmeier and Copil (2016) use variables to track both the starting and the ending times of setup operations assuring that there is at most one setup in parallel. The model is adapted to allow production of a given product on more than just a single line in parallel. Furthermore, the authors propose approaches which make it possible to set up a product several times per macroperiod.
Mac Cawley (2014) proposes a model for wine bottling. Macroperiods help to schedule product families. Changeovers from one product family to another cause sequence-independent setup times. For each product family several product sequences are defined in advance. That means, the product sequencing task is reduced to decide which given sequence should be applied in which period. Therefore, it is not possible to explicitly classify this model as a GLSP or CLSD. If there is production on a line, a crew is necessary. All crews are assumed as being identical. Furthermore, there are a maximum number of possible crews in each macroperiod t. A crew is always assigned to a line for a complete macroperiod. The number of crews can be extended or reduced.
2.2 Disjunctive resources with substitutes
The models presented in this subsection also incorporate disjunctive resources, which can be used at most on one line at the same time. However, now it is possible to choose between different substitute resources for a single process, i.e., the resource is not fixed a priori for a given process.
A GLSP model which considers tools as SRs is presented by Almeder and Almada-Lobo (2011). It is predefined which tools (substitute resources) could be used for a certain product–machine combination. Each product–machine combination requires just a single tool. The tool has to be available for the complete time, starting from the changeover before production and ending with the changeover after production. The first step of the synchronization process is to determine which resources are actually used. To accomplish this, the variables for setup states, changeovers and production quantities are extended by tool indices. Based on these variables, it is possible to calculate the starting times of the microperiods, whose lengths can be different on the various production lines, and the tool release times. Further constraints help to avoid overlapping of the line-specific microperiods when the same tool is used. The authors also propose a CLSD formulation which models SRs in a similar way.
Seeanner (2013, pp. 144–148) considers multiple different setup operators in a multistage GLSP formulation. For each setup it can be defined which setup operators are capable of performing this operation, i.e., substitutes are possible. Binary variables record which setup operator actually performs a setup. Thus, it is simple to assure that a setup operator is at most assigned to a single line per microperiod. This approach is valid because the multistage GLSP has an identical microperiod structure across all lines. Since it is possible to start a setup in microperiod \(s-1\) and finish it in microperiod s (period-overlapping setup operations), further synchronization is necessary. Additional constraints assure that a microperiod is long enough to finish the setup that has been started in the preceding microperiod.
Copil (2016, pp. 121–137) adapts the model presented by Tempelmeier and Copil (2016) to consider multiple setup operators. Every setup operator is capable of performing each changeover. Nevertheless, setup times depend on the skill levels of the deployed setup operators. The model is further extended to represent a practical application of a food producing company in a more detailed way.
2.3 Cumulative resources without substitutes
In the following, we describe models which consider cumulative resources, i.e., resources which serve as input to or output from production processes. They can, but not necessarily need to be used by or generated from more than one line at the same time. These resources are non-renewable in the sense defined in Sect. 1. Furthermore, the models are without substitutes, i.e., it is fixed which resources have to be used for or are generated from a certain process.
Kimms and Drexl (1998, pp. 90–91) propose a second extension of their PLSP model (c.f. Sect. 2.1). Here they introduce scarce SRs which are necessary for production and can be consumed by multiple lines in parallel. Parameters define the resource consumption during production. Capacities of these resources are given per interval of periods (e.g., five periods).
Göthe-Lundgren et al. (2002) present a DLSP formulation for an oil refinery. The multistage model considers different production units which can be run in different modes. A “run mode” defines the materials, which are consumed as input, and products, which are generated as output. Changeovers between run modes can be interpreted as setups. The oil refinery consists of a distillation unit and two different hydro-treatment units. Each run mode of a hydro-treatment unit needs a different amount of hydrogen, but the capacity of generating hydrogen (cumulative SR) is limited. Therefore, not every combination of run modes is possible. Furthermore, during the production process unrequested sulfur (cumulative SR) is generated. The capacity to handle this undesired output product is also limited and restricts the choice of run modes. In the general model formulation it is possible to consider R different SRs. Constraints assure that none of the given resource capacities is violated in any period. Persson et al. (2004) modify the model to consider sequence-dependent changeover costs when switching the run mode.
Seeanner (2013, pp. 143–144) extends his multistage GLSP formulation (c.f. Sect. 2.2) to also consider raw materials. Parameters define the consumption of each raw material during the production of one unit of a product. The overall production may not exceed a given capacity of each raw material (cumulative SR).
A group of models can be identified which—either directly in the model formulation or as part of the solution approach—represent a two-stage production process as a single-stage formulation with scarce SRs, i.e., it is possible to neglect the detailed lotsizing and scheduling of this additional production stage and to solely consider the limited input to or output from the other stage. See also Example 2 of Sect. 1. These models will be described in the following:
A GLSP formulation for a problem of the beverage industry is presented by Ferreira et al. (2009). The production scenario consists of multiple tanks and bottling lines. The tanks are used to prepare different flavored liquids which are packaged using the bottling lines. Only one flavor can be prepared in a tank at the same time. Due to technical reasons minimum liquid quantities have to be assured at the tank filling processes. A tank can be connected to several bottling lines at the same time. Sequence-dependent setup times and costs are considered for the changeovers of the bottling lines (e.g., setup of another bottle size) and for the changeovers of the flavors in the tanks. Only empty tanks can be refilled. First, the authors handle this problem using a two-stage model formulation. Additionally, they propose a solution approach based on a single-stage formulation with SRs (liquids in the tanks). The single-stage model also uses binary variables indicating which flavor is in a tank in a certain microperiod. However, it differs from the two-stage model because these variables do not influence the objective function. After having solved the single-stage formulation, the resulting setups are used to constrain the two-stage model.
The formulation of Ferreira et al. (2010) is again based on the GLSP. However, it just takes a single bottling line into account. Although multiple tanks are connected to this line in real-world, it is sufficient to model just a single tank without setup times. The reason is that the next tank can already be prepared while another one is still supplying the bottling line. Nevertheless, minimum fill levels and maximum capacities of the tanks must be respected , i.e., the liquids in the tanks can be defined as secondary resources. Binary variables are used to track which flavor is in each tank in a certain period.
Ferreira et al. (2012) also examine the beverage problem and use a single-stage GLSP formulation with the tankfuls as cumulative SRs. The authors consider a fixed assignment of tanks to bottling lines. However, to put a resulting plan into practice, some kind of further synchronization between tank filling and bottling is necessary. Otherwise, bottling on a line could start before its supplying tank had sufficiently been filled. This is reached by respecting artificial setup times in the single-stage model, which are taken as the maximum of the tank filling setup time and the bottling setup time. Thus, besides the cumulative SRs of the previously mentioned papers additionally disjunctive SRs, similar to Example 4 of Sect. 1, are used. The authors also propose a CLSD formulation with the same approach for synchronization. Maldonado et al. (2014) compare different CLSD formulations for a simplified problem with just a single bottling line and without artificial setup times. Here, the liquids of the tanks are the only SRs to be considered.
Almada-Lobo et al. (2010) formulate a CSLP to handle a planning task in the glass container industry. Multiple parallel molding machines are supplied with melted glass by a furnace. The furnace’s capacity is given in tons per period and the furnace can be inactive, but only at the end of the planning horizon. If the furnace is active, the complete capacity should be used. Otherwise, penalty costs incur. A single-stage formulation, which incorporates the melted glass as an SR necessary for production and setups, is used. Compared to the aforementioned problems from the beverage industry, the information which glass type to melt is known in advance from a midterm planning. Toledo et al. (2013) restrict the lotsizes to discrete values for the same problem. Furthermore, melted glass still flows during idle times and setups and is returned into the furnace, i.e., there is no resource consumption during these times.
Camargo et al. (2012) consider a problem from the process industry. There exist one upstream machine and multiple downstream machines. The products which are produced on the downstream machines are grouped to product families. Each family needs one kind of SR. In each microperiod at most one SR can be produced on the upstream machine. To begin with the authors present a GLSP formulation. Setup times and costs of the upstream machine are omitted, and a variable is introduced indicating which SR is produced on the upstream machine in a certain period. Secondary resources’ maximum capacities are defined in advance per microperiod (flexible length). The authors do not discuss how such capacities of flexible periods of time could be determined for real-world applications. A capacity check assures that these capacities are not exceeded by consumption of downstream machines. Again, synchronization has to ensure that all downstream machines can only use the SR that is currently produced on the upstream machine. This synchronization is performed using a common time grid for all machines. Thus, the starting and ending times of the microperiods are tracked by variables. Additionally, the authors propose another formulation based on the CLSD. Camargo et al. (2014) adapt the problem for the yarn production using a GLSP formulation.
Santos and Almada-Lobo (2012) consider a problem from the pulp and paper mill industry using a GLSP formulation. Microperiod lengths are still flexible but identical across all lines. Given demand only exists for different paper products. Black liquor and virgin pulp result from processing wood chips in a digester. However, only the virgin pulp can be used to produce the paper products. The black liquor has to be concentrated in an evaporator and afterward burned in a recovery boiler to produce energy. Evaporator and boiler both show limited capacities. This limitation has indirect influence on the regular production since the virgin pulp’s output is proportional to the black liquor’s output. Thus, black liquor is the cumulative secondary resource, which, in this case, limits only one production line. Figueira et al. (2013) extend the objective function to maximize the steam output. Furlan et al. (2015) tackle the same problem like Santos and Almada-Lobo (2012), extend the model for parallel paper machines and present a new solution approach.
2.4 Classification scheme and discussion
Table 2 further classifies and summarizes the models described. Table 1 gives an overview of the acronyms used. Besides “shareability” (note that different disjunctive and cumulative SRs can occur simultaneously in the same model) and “substitutability” additional attributes, which distinguish the various approaches found in the literature, help to characterize SRs’ usage in greater detail. These are:
Basic model This attribute specifies which basic model has been extended for the use of secondary resources. Possible values are DLSP, CSLP, PLSP, CLSD, GLSP or just big bucket if neither an explicit assignment to CLSD nor to GLSP is possible.
States concerned Secondary resources may be necessary for production (p) or setups (s) or while setup states of production lines are conserved (c). Note that these tasks “production,” “setup” and “conservation of the setup state” in the following will be termed as “states” if they are generally addressed and as “processes” if they are addressed in connection with a production line and a product that is produced, that is set up or whose setup state is merely conserved. This denomination has also already been used since the beginning of Sect. 2.1. If substitutes are not possible (Sub=wo), the assignment of an SR to a process is unique. Thus, it suffices to list all tasks a model is able to consider. However, if substitutes do exist (Sub=w), two cases may occur:
-
1.
Either the same SR has to be used for several subsequent processes although a substitute would exist. For example, if two alternative tools could be installed during a setup and then be used for production, either the first or the second one had to be used for both processes.
-
2.
Or the substitutes can freely be exchanged. For example, if two workers had the capabilities to execute a setup and monitor the subsequent production process, the first one could do the setup and the second one the monitoring.
In the following, case 1 will be marked by an “-” and case 2 by an “:”. Thus, the first example would be abbreviated as s-p, whereas the second example would be denoted as s:p.
Quantity of different resources There exist model formulations which consider just a limited number of non-identical secondary resources. In most of these cases, there is only one resource like, e.g., a single setup operator who is responsible for all setups. In order to keep the classification scheme compact, our notation will not distinguish whether just a single resource or multiple identical replicates of this resource are available. However, it will be marked if models provide the possibility to consider an unlimited number of different resources.
Resource-to-process relation This attribute provides information about the relation between resources r (only non-identical resources are considered here) and processes pr. There can be a one-to-one (1:1) assignment, i.e., each resource is uniquely assigned to a single process only. For example, a certain mold can only be used to produce a single type of tire. It is also possible that an SR can be assigned to several processes, called one-to-many (1:pr), for example, if a setup operator is able to execute two different setup operations. If multiple types of SRs are necessary for a single process this is named many-to-one (r:1). For instance, this is the case if both a tool and a setup operator are necessary to perform a certain setup operation. Furthermore, there can be a many-to-many (r:pr) assignment, for example, if a tool and a certain setup operator are needed for some setup operation and the same setup operator is also required for another setup operation. The different relationships between SRs and processes are summarized in Fig. 1. Note that all relationships can be represented by a general formulation that is able to model the r:pr relation.
Resource-to-process relation
Industry Most of the models discussed are motivated by real-world applications. These stem from automotive, beverage, consumer goods, food, process and semiconductor industries (in the future, the list has to be extended if further industries are concerned). These industries typically rely on a flow line organization. This is the reason why we will rather use the term “production lines” than “machines” in the remainder of the paper.
Comments This provides additional information, e.g., how many stages are considered in a model. To clarify this, two-stage (2s) and multistage (ms) mean that the model considers two or multiple production stages, respectively. Of course, additionally, secondary resources are considered in both cases. A special case is defined as SR used to represent a two-stage model (SR2s). That is, the second production stage is not planned in detail (see the examples in Sect. 1). Solely the capacity of the second production stage is considered as secondary resource.
Used example This provides information about the secondary resource mentioned in the considered publication. The specified page numbers refer to the considered publication. In the case of cumulative resources, [i] defines that an input is considered as secondary resource and [o] defines that an output is considered as secondary resource.
When inspecting Table 2 and reconsidering Sects. 2.1–2.3, the following conclusions can be drawn:
-
Model for cumulative resources with substitutes is missing We identified models for three types of resources: disjunctive resources without and with substitutes and cumulative resources without substitutes. To the best of our knowledge, there does not exist any publication taking cumulative resources with substitutes into account. Nevertheless, being able to model such a situation might offer significant advantages as shown in the following example. In the spinning industry, one must determine the size and sequence of yarn production lots as well as which cotton bales (secondary resources) will provide fiber blend that ensures quality attributes (e.g., grade, color and fiber lengths) to produce the required yarns. Each blend must be set by means of different combinations of cotton bales. Nevertheless, different cotton bale combinations (substitutes) can be used to fulfill the quality attributes of a yarn.
-
Models cannot be applied to different scenarios The presented models are very specialized. This can easily be explained because most of these models have been tailored to a specific, practical planning problem of a certain company. Then, the advantage is that the model is not bloated by extra features which are needless for this respective company. Nevertheless, it shows the disadvantage that another company with a slightly different planning problem may not be able to also apply such a model.
-
Models might be too complex One very general model formulation is the one of Seeanner (2013). His formulation of disjunctive resources with substitutes can also be used for disjunctive resources without substitutes by a mere variation of the input parameters. However, in this latter case the model includes more variables than actually necessary.
-
Concerned states are limited Another quite general formulation is the one of Almeder and Almada-Lobo (2011). However, it also shows the shortcoming of many other models that with s-p-c always the same SRs have to be used for a sequence of setup, production and conservation. A more general model would be preferable that could handle an s:p:c situation, too, if this occurred in real-world. The model presented in Sects. 3–5 will be capable of handling both cases.
-
Resource-to-process relation is limited When looking at Table 2, it can be seen that models for the most general resource-to-process relation Rpr = r:pr occur quite seldom. No model can be found at all, which is able to represent disjunctive resources with substitutes in a many-to-many relation. Nevertheless, such scenarios are easy to imagine. For example, think of a situation where a tool out of a set of alternative tools and an additional worker with a minimum skill level out of a group of incrementally trained employees are both necessary for production.
To sum up, a general model must be able to represent disjunctive and cumulative SRs with and without substitutes. Nevertheless—to keep the model lean and to leverage solvability—it should be easy to waive unnecessary parts of the model if they are irrelevant for a certain real-world application. It should be possible to define resource usage for each state separately, but also to enforce retention of the same SR. Furthermore, a process should be allowed to require more than just a single SR. Additionally, SRs should be able to be assigned to several processes simultaneously. Such a general model will be presented in the following sections. A classification of this model can be found in the last row of Table 2.
3 Basic model formulation
The first step is to formulate a model that can be used as a basis for all types of SRs. One important aspect, which must already be considered in the basic formulation, is the synchronization of disjunctive resources. To accomplish this we will build on top of the GLSP for heterogeneous parallel production lines (GLSPPL) of Meyr (2002) and Meyr and Mann (2013). This is a single-stage formulation (for multiple stages see the outlook in Sect. 7). The GLSPPL is adapted to a common time structure across all lines as it has been done in the GLSP for multiple production stages (GLSPMS) in order to synchronize the different stages (c.f., Meyr 2004; Seeanner and Meyr 2013; Seeanner et al. 2013). Just one state is allowed per line and microperiod. Thus, the synchronization of disjunctive SRs across the parallel lines of a single stage of production can also be based on a common microperiod time grid. To assure more flexibility, period-overlapping setup times (so-called continuous setups) are allowed. Suerie (2005) applies this approach of spreading long setup times over several consecutive periods of large-bucket and small-bucket models. We adapt his formulation to the GLSPPL as it has in a similar way been done by Seeanner (2013) concerning the GLSPMS.
The production system comprises multiple parallel production lines l (\(l=1, 2, \ldots ,L\)). These production lines are used to produce several “real” products j (\(j=1, 2, \ldots , J\)). An additional product \(j=0\) is added to represent a “neutral state” of a line when it is not set up for a certain real product. There does not exist any demand for this fictitious dummy product. For all other products \(j>0\) a demand \(d_{jt}\) is given for each macroperiod t (\(t = 1, 2, \ldots , T\)). The production coefficient \(a_{lj}\) defines the production time which is necessary to produce one unit of product j on line l. Before production of a product j can take place on line l, a changeover from the previous product i to product j has to be done. These setups cause sequence-dependent setup costs \(s_{lij}\) and times \(st_{lij}\). Shutdown costs to switch to the neutral state of a line l are indicated by \(s_{li0}\). On the other hand, the activation of lines from the neutral state triggers startup costs \(s_{l0j}\). If a line does not produce, it is called “idle”. If a line l is not shut down but nevertheless idle, the current setup state j is merely conserved. This conservation of setup states causes standby costs \(b_{l}\) per time unit. Holding costs \(h_j\) are accounted for inventory of each product \(j>0\) at the end of each macroperiod. Moreover, \(c_{lj}\) defines the production costs which incur when producing one unit of a product j on line l.
The planning horizon is divided into S microperiods. At most one product j can be produced in each microperiod s (\(s=1, \ldots , S\)). Thus, these microperiods are used to define the product sequence. Each macroperiod t consists of \(|S_t|\) microperiods, whereat \(S_t\) defines the set of microperiods within macroperiod t. The first microperiod of a macroperiod has always a fixed starting time \(\overline{w}_s\). Therefore, the lengths of macroperiods are defined by the starting times of fixed microperiods, which are subsumed by the set \(\Phi \). An additional microperiod \(S+1\) is used to represent the end of the planning horizon. Macroperiod lengths represent the production capacities of the lines. Microperiod lengths are flexible and, in our representation, identical for all lines. The common time structure of all lines is realized using variables \(w_s\) which represent the starting times of the microperiods s.
Continuous variables \(x_{ljs}\) and \(\overline{x}_{ljs}\) are used to measure the production quantity of a product j in microperiod s on line l and the idle time, where the setup state is conserved, respectively. Minimum lotsizes \(m_{lj}\) must be respected. \(I_{jt}\) denotes the inventory of product j at the end of macroperiod t. The binary variables \(y_{ljs}\in \{0;1\}\) and \(v_{ljs}\in \{0;1\}\) represent whether there is production of product j on line l in microperiod s and whether there is conservation of the setup state, respectively.
The following variables are necessary to consider continuous setups: \(x^f_{ls}\) defines the (potentially) fractional time of a setup spent on line l in microperiod s. The continuous variables \(z_{lijs}\) take the value 1 if a changeover from product i to product j on line l is completed in microperiod s. Otherwise, their value is 0. If a changeover from product i to product j is spread over several consecutive microperiods, all periods s of this changeover except for this last completion period are marked by a binary variable \(z^c_{lijs}\in \{0;1\}\) taking on the value 1. These microperiods will be denoted as “to be continued (tbc)” in the following. Note that it is important for the resource consideration that the information about the concerned products is known; thus, the indices i and j in the variable \(z^c_{lijs}\) are necessary. Furthermore, two variables are used to accumulate fractional setup times. \(\tau _{ls}\) determines a lower bound of the up to period s cumulated setup times and \(\sigma _{ls}\) defines an upper bound.
All the parameters and variables used in the model are summarized in Table 3. The model formulation is stated below.
Objective function of the GLSPPL with a common time structure:
Constraints of the GLSPPL with a common time structure:
The objective function (1) minimizes the total costs, namely the sum of holding costs, setup costs, production costs and standby costs.
Constraint (2) creates the macroperiod time structure using the fixed starting times \(\overline{w}_s\) of microperiods \(s \in \Phi \). Equation (3) is the typical inventory balancing equation for each macroperiod. Exactly one of the states “setup to be continued,” “setup completion,” “production” or “conservation” is allowed per production line and microperiod (4). This restriction is important to synchronize SRs as will be shown later. Equation (5) defines the length of microperiod s as the difference between the starting time of the following and the current microperiod. The time budget of such a microperiod must be completely used for either production or conservation of the setup state or for setups.
The values of the binary variables \(y_{ljs}\) and \(v_{ljs}\) are defined by constraints (6) and (7), respectively. If there is production \(x_{ljs}>0\) or conservation of a setup state \(\overline{x}_{ljs}>0\), the corresponding binary variable takes the value 1. Constraint (8) assures that positive setup time can only be charged if a setup takes place. In these three types of constraints, the planning horizon \(\overline{w}_{S+1}\) serves as a big number linking the continuous with the binary variables.
Similarly to Koçlar and Süral (2005), it is sufficient to fulfill the minimum lotsizes during the first two microperiods after a setup (9). This approach offers more flexibility than just using \(x_{ljs}\) on the left-hand side. Thus, for instance, conservation of the setup state in the first microperiod after a setup is possible.
Equation (10) ensures the correct flow of the different states of a line. For example, if product j has been set up in period \(s-1\) (left-hand side = 1), but is not needed any longer in the following period (\(y_{ljs} = v_{ljs} = 0\)), a changeover to another product i has to be started in period s, which can either also be finished in period s (i.e., \(\sum _{i\ne j}z_{ljis} = 1\)) or has to be continued in period \(s+1\) (i.e., \(\sum _{i\ne j}z^c_{ljis} = 1\)). Note that Eq. (11) and not Eq. (10) is responsible for the correct flow of the tbc periods. Nevertheless, Eq. (10) includes a \(\sum _{i \ne j}z^c_{lji,s-1}\) on the left-hand side. Otherwise, it would never be possible to switch from a tbc period to the completion of a setup.Footnote 3 Further note that because of (10), in any optimal solution, the variables \(z_{lijs}\) will only take zero or one as values.
The remaining constraints are necessary to model the period-overlapping setups. Constraint (11) assures that a continuous setup is not interrupted. Once started (\(z^c_{lij,s-1} = 1\)) in or before period \(s-1\), because of (4), it either has to be continued (\(z^c_{lijs} = 1\)) or finished (\(z_{lijs} = 1\)) in the following period s. Constraint (12) ensures that sufficient setup time \(\tau _{ls}\) will be accumulated until the setup has been completed in period s. The accumulation is put into practice by constraint (13). It finally needs to reach \(st_{lij}\), but can at most be increased from a preceding period to its subsequent period by the fractional setup time \(x^f_{ls}\). Reading constraint (13) as \(x^f_{ls} \ge \tau _{ls} - \tau _{l,s-1} \forall l,s\) clarifies why \(\tau \) is called a “lower bound” for the setup time to be spent. Because of (5), its increment has to be reserved on line l for each continuous setup period affected. After a setup has been completed (\(z_{lij,s-1} = 1\)) in a period \(s-1\), at the beginning of the next period s the cumulated setup time \(\tau \) needs to be reset to zero. Constraint (14) does this indirectly by limiting the setup time \(\tau _{ls}\), that has been accumulated until the end of period s, to the fractional setup time \(x^f_{ls}\) accounted for period s. The added term \(\overline{w}_{S+1}\sum _{i,j}{z^c_{lij,s-1}}\) turns this constraint non-active in tbc periods.
If the costs for conserving the setup state were very high, the model presented so far would artificially stretch the setup times and accumulate more fractional setup times \(x^f_{ls}\) than actually necessary. If this shall be prevented, penalty costs for \(x^f_{ls}\) could be imposed or constraints (15)–(17) could be introduced. Like \(\tau _{ls}\) the variables \(\sigma _{ls}\) accumulate the fractional setup times. Constraint (15) forces the \(\sigma _{ls}\) of period s to sum the preceding period’s \(\sigma _{l,s-1}\) and the current period’s fractional setup time \(x^f_{ls}\) as long as the setup has not been completed in the preceding period (\(\sum _{i,j}st_{lij}z_{lij,s-1} = 0\)). If the setup has been completed, \(\sigma _{ls}\) is reset to zero. Reading (15) as \(x^f_{ls} \le \sigma _{ls} - \sigma _{l,s-1} + \sum _{i,j}st_{lij}z_{lij,s-1}\) illustrates why \(\sigma \) is called an “upper bound” on the fractional setup times. According to constraint (16), the accumulated setup time \(\sigma _{ls}\) itself is bounded by \(st_{lij}\) if a changeover from product i to product j has been completed (\(\sum _{i,j}z_{lijs} = 1, \sum _{i,j}{z^c_{lijs}} = 0\)) in period s. In tbc periods (\(\sum _{i,j}z^c_{lijs} = 1, \sum _{i,j}z_{lijs} = 0\)), however, constraint (16) does not show any effect. Equation (17) finally forbids unfinished setups at the end of the planning horizon (see also Table 3).
4 Extension for secondary resources
The following subsections introduce practically relevant extensions to the base formulation to consider secondary resources. We structure the presentation according to the four different types of SRs that emerged from the literature review in Sect. 2. If all presented constraints are simultaneously used in a single model, each type of SR can be represented. We indicate this by using different indices for the different types of SRs. Of course, it is also possible to neglect some type of SR and omit its corresponding constraints if this was sufficient for a certain industrial application. Some additional optional features, helping to further adapt the model formulation to industrial needs, are presented in Sect. 5.
4.1 Disjunctive resources without substitutes
The basic model stated up to now will in the following be extended to consider disjunctive resources without substitutes. An example would be a scenario with two setup operators who are necessary to perform setups, a tool which is bounded to the machines during setups, production and conservation of setup states and a worker who is responsible for the machine during production. In terms of our classification scheme of Sect. 2.4, a process may need several SRs, i.e., multiple resources are considered and the resource-to-process relation is flexible (r:pr). Nevertheless, there are no substitutes.
There are several disjunctive resources \(p=1, 2, \ldots , P\). We assume that each resource is available for the complete planning horizon. For each potential process (conservation of the setup state of product j, production of product j and changeover from product i to j) it is possible to define whether resource p is necessary or not by introducing further binary parameters \(b^{c}_{jp}\), \(b^{p}_{jp}\) and \(b^{s}_{ijp}\), respectively. Of course, these parameters could also be declared as line-dependent if necessary. These additional parameters are summarized in Table 4. (New variables are not needed.) The necessary additional constraint is stated below.
Additional constraint for disjunctive resources without substitutes:
Constraint (18) avoids double usage of SRs and thus synchronizes the use of SRs across all parallel lines. Since there is a common time structure with exactly one state per microperiod, it is sufficient to check that each SR p is used on at most one line in every microperiod s. If necessary, the right-hand side of constraint (18) can be substituted by a parameter indicating the number of replicas which exist of resource p. Note that—now and in the following—for ease of simplicity we assume that there do not occur any transportation times if an SR is transferred from one production line to another.
Figure 2 shows an exemplary production plan with a common time structure and a single state per microperiod. If resource \(p=1\) is necessary for the setup on line 1 in microperiod 1, this resource cannot be used on another line in the same microperiod. A binary parameter like \(b^{s}_{ijp}\) ensures that several setups can be executed in the same microperiod if they use different SRs. Thus, both setups (from product 1 to 2 on line 1 and from product 3 to 4 on line 2) in microperiod \(s=1\) are possible if there are two different tools \(p=1\) and \(p=2\) with \(b^{s}_{121} = b^{s}_{342} = 1\).
Example production plan with common time structure and exactly one state per line and microperiod
4.2 Disjunctive resources with substitutes
Now, the base model (Eqs. 1–17) is extended to consider disjunctive resources with substitutes. For instance, it is possible to choose whether worker 1 or worker 2 performs a given setup. This opportunity is of particular interest if the workers are heterogeneous, e.g., if they have different skills and can take care of different processes. For instance, worker 1 can perform every setup operation and worker 2 can only perform simple setup operations. Then, substitutability leads to more flexibility to construct feasible production plans. Again, the formulation is capable of handling the most general case concerning the resource-to-process relations (r:pr). In this section, we only consider the case s:p:c where substitutable SRs may be switched from period to period. Later on in Sect. 5.2, we will present an extension for the s-p-c case.
Resources are defined using the index \(q=1, 2, \ldots , Q\). The index \(u=1, 2, \ldots , U\) distinguishes different skills, e.g., the skill of a worker to execute a simple or a more complex setup or the skill of a tool to execute a certain production process. The substitute set \(\Theta _{u}\) contains all resources q with skill u which are substitutes for each other (see also Fig. 3 for a better understanding). For example, if worker 1 is defined as \(q=1\) and worker 2 as \(q=2\), both are substitutes for each other because both show skill \(u=1\), then \(\Theta _{1} = \{1;2\}\). A process may require several skills simultaneously. For example, a low-skilled worker (\(u=1\)) and a 9 mm drill (\(u=2\)) may be necessary simultaneously to produce a certain product \(j=1\). The process sets \(\Omega _{j}^{c}\), \(\Omega _{j}^{p}\) and \(\Omega _{ij}^{s}\) describe which skills u are necessary for conservation of setup state j, for production of product j and for a changeover from product i to product j, respectively.Footnote 4 Then the process set \(\Omega _{1}^{p} = \{1;2\}\) represents the simultaneous necessity of both skills in the above example.
A resource can have more than one skill and thus belong to more than one substitute set. For example, worker \(q=1\) may be able to execute a simple setup (\(u=1\)) and a complex setup (\(u=3\)), whereas worker \(q=2\) is only able to execute the simple setup (\(u=1\)). In addition, a 9 mm diamond drill \(q=3\) may be able to drill 9 mm holes in soft (\(u=2\)) and hard (\(u=4\)) surfaces, whereas a 9 mm metal drill \(q=4\) may only be able to perforate soft surfaces (\(u=2\)), altogether resulting in the four substitute sets \(\Theta _{1} = \{1;2\}\), \(\Theta _{2} = \{3;4\}\), \(\Theta _{3} = \{1\}\) and \(\Theta _{4} = \{3\}\). However, for ease of simplicity, we assume that the same resource cannot be in two different substitute sets of the same process set. When looking at the graphical representation in Fig. 3, this would mean that a resource cannot be found more than once in the large circle (e.g., \(q=1\) cannot be in \(\Theta _{u=1}\) and \(\Theta _{u=2}\) because they are both part of \(\Omega ^p_{j=1}\)). Relaxing this restriction would lead to significantly more variables in the model. As the above example demonstrates, this assumption is not really crucial because reasonable skill requirements can nevertheless be modeled, e.g., production processes needing low-skilled workers and simple drills (\(\Omega _{1}^{p} = \{1;2\}\)) as well as processes needing high-skilled workers and complex drills (\(\Omega _{2}^{p} = \{3;4\}\)).
Example for substitute consideration
It is necessary to track which resources are used in order to ensure the correct synchronization of substitutes. Thus, three new variables are introduced: \(y_{lqs}^{c}\) indicates whether resource q is used to conserve a setup state on line l in microperiod s, \(y_{lqs}^{p}\) indicates if resource q is used during a production process on line l in microperiod s and \(y_{lqs}^{s}\) triggers the use of resource q to perform a setup on line l in microperiod s. Additional symbols are summarized in Table 5, and the additional constraints are stated afterward.
Additional constraints for disjunctive resources with substitutes read:
For each skill u of process set \(\Omega _{j}^{p}\), inequality (19) attaches a suitable SR if product j needs to be produced on line l in microperiod s. As an example, let substitute set 1 again consist of workers \(q=1\) and \(q=2\) with skill \(u=1\) (\(\Theta _1=\{1; 2\}\)) and substitute set 2 consist of tools \(q=3\) and \(q=4\) with skill \(u=2\) (\(\Theta _2=\{3; 4\}\)), respectively. Product 1 is produced (\(y_{l1s}=1\)), requiring both skills (\(\Omega _1^p = \{1;2\}\)). On the one hand, (19) turns into \(\sum _{q \in \Theta _1} y^{p}_{lqs} \ge 1\), forcing \(y^{p}_{l1s}\) or \(y^{p}_{l2s}\) to be set to 1. On the other hand, (19) yields \(\sum _{q \in \Theta _2} y^{p}_{lqs} \ge 1\). Consequently, \(y^{p}_{l3s}\) or \(y^{p}_{l4s}\) must take 1, assuring that at least one resource out of each substitute set is assigned to the production process of product 1.
The variables could also be continuous. This would lead to production plans with processes performed by combinations of disjunctive resources, e.g., \(30\%\) of the work is done by worker 1 and \(70\%\) of the work is done by worker 2. This is possible (when assuming zero transfer times), but normally not desired. Inequalities (20) and (21) are constructed in the same way as (19). They assure correct standbys and setups, respectively. Up to now, the decision variables only indicate the usage of the resources. Inequality (22) enforces that the same resource q cannot be attached to several lines in the same microperiod.
Note the difference between the case without (Sect. 4.1) and with (Sect. 4.2) substitutes: In (18), resource usage only depends on whether the process is active or not. Inequalities (19)–(21) additionally provide the possibility to choose which resources are used if a process is active.
4.3 Cumulative resources without substitutes
In this subsection, the model is extended to consider cumulative resources without substitutes, e.g., a raw material which is used for parallel production of two different products on two lines. Raw materials can also be necessary during setups for test runs and adjustment processes of the production lines. It is predefined how many units of a resource are necessary to perform a certain process. Storing of resources is not possible, i.e., if the resource’s capacity is not completely needed in a certain macroperiod, the remaining capacity cannot be used in the following macroperiod. An extension for storing cumulative SRs is discussed in Sect. 5. The resource-to-process relation is general (r:pr). The resources’ availability is already known.
The index \(r=1, 2, \ldots , R\) denotes the different resources. Each resource has a given capacity \(K_{rt}\) per macroperiod t. The consumption of resource r is defined by parameters \(e^{c}_{jr}\), \(e^{p}_{jr}\) and \(e^{s}_{ijr}\) for conservation, production and setup processes. Table 6 shows concrete definitions of these additional parameters.
With the above assumptions, the additional constraint (23) suffices to model cumulative resources without substitutes:
They assure that the aggregate capacity of each resource r is respected in every macroperiod t. Since we only consider an SR’s aggregate capacity per macroperiod in this section, it is sufficient to assume that the total amount \(e^{s}_{ijr}\) of a cumulative setup resource r (e.g., a raw material used for cleaning) will be merely consumed in the last microperiod of a continuous setup. A more detailed modeling of permanently used SRs is discussed in Sect. 5.
4.4 Cumulative resources with substitutes
Finally, cumulative SRs with substitutes are considered. For example, it is possible to produce product 1 using raw material 1 or raw material 2. The index \(n=1, 2, \ldots , N\) defines the different cumulative resources. The index \(o = 1, \ldots , O\) distinguishes different properties these resources may show, e.g., whether they stem from a local or a global supplier or from organic or conventional cultivation. Similarly to \(\Theta _u\) in Sect. 4.2, substitute sets \(\Xi _o\) are introduced, which list the resources n that share property o and can alternatively be used. For example, the raw materials of a conventional final product could stem from both conventional and organic cultivation, whereas the raw materials of an organic final product would not allow such a substitution. We assume that the resources of a substitute set can be combined to fulfill a process, e.g., if 30 units of product 1 are produced in microperiod s, 10 of them can be produced using raw material 1 and 20 using raw material 2.
The properties o that are necessary for conservation of the setup state of product j, for production of product j, and for setups from i to j are declared by the process sets \(\Lambda _{j}^{c}\), \(\Lambda _{j}^{p}\) and \(\Lambda _{ij}^{s}\), respectively. \(K^c_{nt} \) denotes the overall capacity of resource n in macroperiod t. \(f^c_{jo}\) denotes the overall amount of SRs with property o that is necessary to conserve setup state j for one time unit. \(f^p_{jo}\) and \(f^s_{ijo}\) state the amount of SRs with property o necessary for the production of one unit of product j and during a setup from product i to j, respectively. Similarly to the case of cumulative resources without substitutes, \(f^s_{ijo}\) is only used in the last microperiod of a continuous setup. The continuous variables \(x_{lns}^{c}\), \(x_{lns}^{p}\) and \(x_{lns}^{s}\) distinguish the consumption of resource n on line l in microperiod s for conservation, production and setups. This notation is summarized in Table 7.
Additional constraints for cumulative resources with substitutes:
Inequality (24) determines the values of variables \(x^{p}_{lns}\). It is assured that enough resource quantities from substitute set \(\Xi _o\) are reserved for the production quantity \(x_{ljs}\). These quantities can be fulfilled by only one resource or a combination of different resources of the substitute set of property o. Note that here the same resource may be in several substitute sets of the same process set. For example, assume that multivitamin juice (\(j=1\)) has to be mixed from orange and pineapple concentrate. Orange concentrate can be bought from a Spanish (\(n=1\)) and Mexican (\(n=2\)) supplier, pineapple concentrate can be bought from a Thai (\(n=3\)) and Brazilian (\(n=4\)) supplier. The juice needs to have shares of at least 20 % of both orange (\(o=1\)) and pineapple (\(o=2\)) concentrate (\(f^{p}_{11} = f^{p}_{12} = 0.2\)). However, the overall share of fruit concentrate (\(o=3\)) has to be at least 50 % (\(f^{p}_{13} = 0.5\)). Then, the three substitute sets \(\Xi _{1}=\{1; 2\}\), \(\Xi _{2}=\{3; 4\}\) and \(\Xi _{3}=\{1; 2; 3; 4\}\) result, which all belong to the same process set \(\Lambda _{1}^{p}=\{1; 2; 3\}\).Footnote 5
Inequalities (25) and (26) are constructed in the same way and assure that enough resources are assigned for the conservation of setup states and for the setups, respectively. Equation (27) ensures that the available resource capacities \(K_{nt}^c\) are respected for each resource n in each macroperiod t.
5 Considering additional features
This section demonstrates how the model can be applied and how it may easily be adapted to incorporate further SR-relevant features. For some companies, these features can be of great help to create realistic production plans. It is possible to combine the constraints of the different scenarios described in Sects. 4.1–4.4. For instance, if a company has disjunctive resources with substitutes and cumulative resources without substitutes, as well, Eqs. (1)–(17), (19)–(22) and (23) can be combined to address this case.
Rather complex extensions are explained in sufficient detail in Sects. 5.1–5.4. More obvious extensions are just briefly sketched in the following:
-
Capacity restriction of disjunctive resources Sect. 4.1 assumed that a disjunctive SR p is always available for the complete planning horizon. In the literature of disjunctive resources without substitutes, this assumption is sometimes relaxed (c.f. Table 2). For example, a setup operator p might only be available for 7 h within an 8 h macroperiod. Introducing a new parameter \(K^d_{pt}\) denoting the available capacity of SR p in macroperiod t, enables to represent this case. An additional variable is necessary to track the products involved in a setup operation on each line in each microperiod, since the variable of the fractional setup time \(x^f_{ls}\) does not provide this necessary information.
-
Capacity restriction of cumulative resources for a continuously provided resource If non-substitutable cumulative resources are provided in a continuous manner, e.g., because there is a continuous flow from a pipeline, it might not be sufficient to respect the SR’s capacity only per macroperiod in an aggregate manner, as it has been done using constraint (23) of Sect. 4.3. In this case, the SR’s capacity needs to be modeled in more detail, e.g., on a microperiod basis. Introducing a flow rate \(Kf_r\) (measured in units of secondary resource r per unit of time) helps to implement this case.
-
Inventory balancing of cumulative resources If unused cumulative resources can be stored, the development of the resulting inventories should be tracked over time. This can be done on both a macro- or microperiod basis by introducing variables \({\bar{I}}_{rt} \ge 0\) or \({\hat{I}}_{rs} \ge 0\) representing the inventory of resource r at the end of macroperiod t or microperiod s, respectively. Let \(\bar{K}_{rt}\) now denote a predefined, given supply of resource r in macroperiod t (e.g., by a midterm contract with a supplier of r), and \(\hat{Kf}_{r}\) denote a constant inflow rate of resource r per unit of time (e.g., from a preceding, independent stage of production). Then, standard inventory balancing constraints can be constructed using \(\bar{K}_{rt}\) and \(\hat{Kf}_r(w_s - w_{s-1})\) as inflow of the inventory balance per macro- and microperiod, respectively.
5.1 Split of setups into dismounting, cleaning and mounting
In some industrial settings it may be important to split a changeover from product i to product j into a dismounting operation of product i, a cleaning operation and a mounting operation of product j. Sections 4.1 and 4.2 assume that disjunctive resources (e.g., cutting tools), which are necessary for product i, and disjunctive resources, which are necessary for product j, are assigned to the production line for the complete setup from product i to j. This assumption can be too restrictive. For instance, if the overall setup time is 6 h and dismounting, cleaning and mounting last 1, 2 and 3 h, the disjunctive resources which are necessary for product i will be assigned to the production line for 6 h. By splitting the operation into dismounting, cleaning and mounting, the resources only necessary for product i already get available 1 h after starting the changeover.
The three new states “dismounting,” “cleaning” and “mounting” replace the state “setup”. We introduce the identifiers D, E and M to distinguish these states. For example, the former aggregate setup time \(st_{lij} = 6\) will be replaced by \(st^{D}_{lij} = 1\) for dismounting, \(st^{E}_{lij} = 2\) for cleaning and \(st^{M}_{lij} = 3\) for mounting. Sequence dependency of these times is still important, as it could be the case that some tools, which have been necessary for product i, are still needed for product j and can be left mounted, whereas others have to be dismounted. This fact enforces to track the sequence. Note that the restriction of having exactly one state per line and microperiod is still valid. Furthermore, we assume that these three processes are always in the order dismounting \(\rightarrow \) cleaning \(\rightarrow \) mounting and that there is no idle time in between. Nevertheless, each of these three states may be spread over several periods.
Besides setup times further parameters (\(z_{lij0}\), \(z^{c}_{lij0}\); cf. Table 3) and variables (\(\sigma _{ls}\), \(\tau _{ls}\), \(x^f_{ls}\), \(z_{lijs}\), \(z^{c}_{lijs}\)) have to differentiate the three new states in order to adapt the basic model accordingly. We use the same logic to distinguish them, but introduce an abbreviation for our notation: An asterisk * marks that a constraint has to be executed for each of the three states with the corresponding state-specific parameters and variables. For example, \(x^{f*}_{ls} \ge 0 \,\, \forall l, s, *\) would abbreviate the nonnegativity constraints \(x^{fD}_{ls} \ge 0, x^{fE}_{ls} \ge 0\) and \(x^{fM}_{ls} \ge 0 \,\, \forall l,s\) of the fractional setup times \(x^{fD}_{ls}\), \(x^{fE}_{ls}\) and \(x^{fM}_{ls}\) of the states “dismounting,” “cleaning” and “mounting”.
Compared to basic model’s objective (1) the only change of the new objective function (28) is that the \(z_{lijs}\) are substituted by \(z^M_{lijs}\):
The adapted constraints of the basic model (1)–(17) are presented and explained in the following (constraints (2), (3), (6) and (7) are still valid):
Equation (4) is substituted by (29) to assure that at most one state is allowed per microperiod and production line. The capacity restriction (5) is adapted to (30) in order to respect all five states that are now possible. Inequality (8) is changed to (31) to respect all three states involved in a setup. As in (9), the minimum lotsizes of (32) still have to be produced within two subsequent microperiods. However, now \(z^M_{lijs}\) indicates the end of a setup.
The correct flow of states is assured by (33)–(36) which substitute (10) and (11). Equation (33) switches from a preceding state in period \(s-1\) to one of the states “production,” “dismounting” or “conservation” in period s. If a setup had been started in \(s-1\) by switching to the dismounting state, constraint (34) enforces a correct flow of states during a continuous dismounting. Likewise, continuity of cleaning and mounting is ensured if the \(*\) in (34) is substituted by E and M, respectively. Constraint (35) enables a change from dismounting to cleaning. Constraint (36) enforces the subsequent transition from cleaning to mounting. If a mounting had been completed in period \(s-1\) because of \(z^M_{lij,s-1}=1\), Eq. (33) again controls the flow of states until the next setup starts with a dismounting operation. For example, let us assume that a changeover takes place from product \(i'\) to product \(j'\) where a continued dismount is finished in period \(s'\), i.e., \(\sum _{i \ne j}z^{cD}_{lji,s-1}=1\) and \(\sum _{i\ne j}z^D_{ljis}=1\) for \(j=i'\) and period \(s=s'\). Then the left-hand side of (33) has to become 0 for all j in period \(s=s'+1\) because of (29). Furthermore, \(z^{cE}_{li'j',s'+1}\) or \(z^{E}_{li'j',s'+1}\) have to take the value 1 because of (35). This is not hindered by (33) because none of the variables indicating a cleaning operation appear in (33). If this cleaning ends in period \(s'' \ge s'+1\) by \(z^E_{li'j's''} = 1\), a mounting process has to start in period \(s''+1\) (either \(z^{cM}_{li'j',s''+1} = 1\) or \(z^M_{li'j',s''+1} = 1\)) because of (36). If this mounting is finished in some period \(s''' \ge s''+1\), in the following period, the left-hand side of (33) becomes 1 for product \(j=j'\) and production, conservation (or dismounting) of product \(j'\) might start (see Table 8). All in all, \(\sum _{i \ne j}z^{cD}_{lji,s-1}\) on the left-hand side of (33) serves the same purpose as \(\sum _{i \ne j}z^{c}_{lji,s-1}\) did in (10).
Constraints (37)–(42) replace (12)–(17), however, mirrored for the states “dismounting,” “cleaning” and “mounting”.
The constraints for the different resource types can easily be adapted to consider dismounting, cleaning and mounting, as well. As an example, this is done for disjunctive resources with substitutes (c.f. Sect. 4.2). The process sets \(\Omega ^s_{ij}\), representing the information which skills u are necessary for a changeover from product i to product j, are replaced by new process sets \(\Omega ^{D}_i\), \(\Omega ^{E}_j\) and \(\Omega ^{M}_j\) representing the information which skills u are necessary during dismounting of product i and cleaning and mounting of product j, respectively. The variables \(y^s_{lqs}\) are replaced by corresponding variables \(y^*_{lqs}\).
Then, constraints (21) and (22) of Sect. 4.2 have to be replaced by the following adapted constraints (43)–(45) and (46):
Constraints (43)–(45) determine which disjunctive SRs of the substitute sets \(\Theta _u\) are actually used in the different states. Because of (46), each SR q is at most applied once per microperiod s.
5.2 S-p-c model for disjunctive substitutes and splitting of setups
In this section, we introduce additional constraints to represent the s-p-c case. If splitting of setups in dismounting, cleaning and mounting is allowed, too, this means that it is mandatory that the same resource (e.g., a tool) is used during all three states.
Constraints (47)–(50) assure that the same resource is used during all subsequent microperiods of this sequence of processes:
Constraint (47) assures that an SR q, which is used for dismounting on line l in microperiod \(s-1\), is also used for dismounting on the same line in microperiod s. This flow can only be interrupted if dismounting also had been finished in microperiod \(s-1\), i.e., if \(\sum _{i,j\ne i}z^D_{lij,s-1}=1\). Constraint (48) works in the same way to consider resource flows during mounting. The resource flow during production and conservation of a setup state is respected using constraint (49). They allow an arbitrary change between the states production and conservation until dismounting begins. Constraint (50) enforces that mounting can only be followed by mounting or the sequence defined by (49). Overall, the resource can only be released from this production line using a dismounting operation.
If a cleaning process required the same SR q during all cleaning periods, this could be modeled in a similar fashion.
5.3 No substitution of cumulative resources during a production lot
The formulation in Sect. 4.4 allows a combination of substitutable cumulative resources when producing a certain product. Sometimes, it is not desired to switch between alternative raw materials while producing a single lot. For instance, one would like to avoid switching the providing tank several times for a single production lot lasting just a few minutes. To hinder substitution within a single lot, the model from Sect. 4.4 needs to be adapted. We just sketch the general idea but do not present the complete model:
The additional binary variables \(y_{lns}^{bp}\) are set to 1 if resource n is used for production on line l in microperiod s (otherwise 0). Constraint (51) assures this by means of a big constant M. To forbid switching, at most one type of SR of each substitute set \(\Xi _{o}\) is allowed per line, microperiod and property o (52). If desired, analogous constraints must be formulated for the other potential states of the line, too. Since a production lot may span over several microperiods, it is still possible that line l uses one raw material of substitute set \(\Xi _{o}\) in microperiod s and another one in microperiod \(s+1\). To prevent this, flow constraints similar to (49) are necessary.
5.4 All lines must consume the same resource
The following extension represents the case of Camargo et al. (2012). The authors consider a scenario where all production lines must consume the same resource at the same time. This way they model a furnace which feeds several lines in parallel. The material can differ from period to period. Our model from Sect. 4.3 can be used as a basis. Thus, cumulative resources without substitutes are considered, and the following constraint is added:
The left-hand side of (53) constitutes the total consumption of resource r on all lines in microperiod s, whereas the brackets of the right-hand side constitute the consumption of the same resource in the same microperiod, but only on line l. Thus, with M again being a large positive constant, (53) ensures that all other lines are forced to use resource r if at least one line uses this resource. Note that a line may still require more than just a single SR.
6 Examples
The following examples demonstrate the functionality of the model. The focus is on the secondary resources. Thus, the basic production scenario is very simple and all models are kept small in order to remain comprehensive. In Sect. 6.1 disjunctive resources without substitutes are addressed. The subsequent section is devoted to disjunctive resources with substitutes. Section 6.3 addresses cumulative resources with substitutes. Afterward an example with all types of resources is presented. The final scenario of Sect. 6.5 requires continuous setups.
The exemplary models have been implemented using GMPL 4.50 as a modeling language and GLPK 4.55 as a solver. All experiments have been performed on an IntelCore i5-4300 CPU 1.9 GHz, 8 GB RAM. However, computation time is not the focus of this section, but rather the flexibility of the underlying mixed-integer programming models.
6.1 Disjunctive resources without substitutes
The basic production scenario comprises two lines and two products (plus a product \(j=0\) to represent the neutral state). It lasts 1 time unit to produce 1 unit of each product. Production of product 1 is only possible on line 1, and product 2 can be produced exclusively on line 2. Production costs are 2 monetary units per unit of each product. Setup costs are set to 1 monetary unit, and setup times are set to 1 time unit for every product combination. Both lines are in the neutral state (\(j=0\)) at the beginning of the planning horizon. Two macroperiods containing three microperiods each are considered. Each of them has a capacity of 10 time units. If 1 unit of a product is stored for one macroperiod, holding costs of 1 monetary unit occur. Standby costs are zero and the demand of product 1 and 2 is 8 units, each, at the end of the second macroperiod. Minimum lotsizes are set to one. The optimal production plan without consideration of secondary resources is presented in Fig. 4.
Production plan without consideration of secondary resources
The length of microperiods \(s=1\) and \(s=2\) is zero. In microperiods \(s=3\) and \(s=4\) the initial setup state (\(j=0\)) is conserved (standby) on both lines. Microperiod \(s=5\) is used to perform the setups from product 0 to 1 on line 1 and from product 0 to 2 on line 2. The last microperiod has a length of 8 time units and is used for production on both lines. The total costs are 34 monetary units.
Now, there are three different secondary resources: workers A and B, and tool C. Worker A is necessary for every setup which involves product 1, and worker B is necessary for every setup which involves product 2. Tool C is necessary for every setup which involves product 1 and 2 and for production and standby of the products 1 and 2. The production plan resulting from solving model (1)–(18) is shown in Fig. 5.
Production plan with consideration of disjunctive resources
Since tool C is necessary for the production of both products, it is not possible to produce them at the same time. Furthermore, tool C is also necessary for the standby of the products. Thus, it is not possible that line 2 stays set up for product 2 after production. Additional costs occur due to the changeover from product 2 to 0 in microperiod 4. The tool is still necessary during this setup operation; thus, this setup has to be finished before the setup on line 1 can start in microperiod 5. Due to preproduction in microperiod 3 holding costs of 8 monetary units occur. Nevertheless, an optimal production plan, which would be feasible in this practical application, has been created.
6.2 Disjunctive resources with substitutes
The considered scenario is similar to the scenario described in Sect. 6.1. The only difference is the existence of an additional tool D, which can be installed instead of tool C for both products. For workers A and B, constraint (18) of the model without substitutes can still be used. Nevertheless, it is also possible to apply the constraints for resources with substitutes. In this case, there would be just one resource in the substitute set and the model would involve unnecessary variables. However, for tools C and D the formulation of Sect. 4.2 is mandatory. The resulting production plan is presented in Fig. 6.
Production plan with consideration of disjunctive resources with substitutes
As can be seen, complete production takes place in macroperiod \(t=2\). Thus, the total costs are 34 monetary units. The usage of tools C and D is indicated by the variables \(y^s_{lqs}\), \(y^p_{lqs}\) and \(y^c_{lqs}\). As shown in Fig. 6, each resource is used at most on one line in each microperiod.
Since a frequent switching of SRs is not always welcome, in the following we apply the s-p-c formulation of Sect. 5.2. We assume that dismounting, cleaning and mounting lasts 1 time unit, each. Substitute set 1, consisting of tools C and D, is necessary during the mounting and production of the products \(j=1\) and \(j=2\). The resulting production plan is presented in Fig. 7.
Production plan of the s-p-c case
Setups are split into dismounting in microperiod 2, cleaning in microperiod 4 and mounting in microperiod 5. Production takes place in microperiod 6. The total costs are 34 monetary units. Tool C is used on line 1 during mounting and production. Tool D is used on line 2 for the same sequence of states. A comparison with Fig. 6 reveals that s-p-c model works as expected. The schedule of Fig. 7 is also a feasible and optimal plan for the previous model. However, as already mentioned, the schedule of Fig. 6 would not be feasible for the s-p-c case.
6.3 Cumulative resources with substitutes
Now, the basic production scenario is extended by cumulative SRs only. We assume that 2 units of resource 1 (e.g., a raw material) are necessary to produce product 1. Furthermore, we assume that 3 units of resource 1, 2 or 3 are necessary to produce product 2. The model with substitutes of Sect. 4.4 is used. Substitute set 1 consists of resource 1 and substitute set 2 consists of resources 1, 2 and 3. The availability of resource 1 is 10 units per macroperiod. Each of the two other resources has an availability of 5 units per macroperiod. The resulting production plan is presented in Fig. 8.
Production plan with consideration of cumulative resources
The setups from product 0 to 1 and from product 0 to 2 take place in microperiod 2. Product 1 is set up on line 1 and product 2 on line 2. Production of 4 units of each product takes place in microperiod 3. Note that resource 1 is used on both lines in parallel in microperiod 3 as expected under the setting of cumulative resources. As can be seen, the resources of substitute set 2 are combined to fulfill the requested quantity of resources to produce 4 units of product 2. The missing units of products 1 and 2 are produced in macroperiod 2. Since the preproduction of 4 units each is necessary due to resource restrictions, the costs sum up to 42 monetary units including 8 monetary units for storing 4 units of product 1 and 4 units of product 2.
6.4 A combination of different types of resources
The following scenario demonstrates the combination of disjunctive and cumulative SRs. Furthermore, it also considers the case that a process needs resources of more than just one substitute set. The basic scenario is not changed. A setup which involves product 1 needs the following resources: one worker of a group of two high-skilled workers (substitute set \(\Theta _1\) including disjunctive resources 1 and 2), one worker of a group of three lower-skilled workers (substitute set \(\Theta _2\) including disjunctive resources 3, 4 and 5) and one crane (disjunctive resource 6) whereof just one replica exists. There are two different substitute sets of cumulative resources (\(\Xi _1\) and \(\Xi _2\)), each consisting of two raw materials. A setup consumes 10 units of each of these substitute sets to perform test runs and adjustments of the production line. Production of product 1 requires 2 units of each of these substitute sets for each produced unit. Furthermore, one worker of substitute set \(\Theta _2\) is necessary. Setup and production of product 2 require exactly the same resources. Disjunctive resources are available during the complete planning horizon. Raw materials 1 and 2 (substitute set \(\Xi _1\)) are limited to 20 units per period, each. The same holds for substitute set \(\Xi _2\) (raw materials 3 and 4). Figure 9 shows the resulting production plan.
Production plan with different types of resources
The total costs are 34 monetary units. As can be seen, all requirements are considered. For instance, disjunctive resource 3 is used for production on line 1, and disjunctive resource 5 for production on line 2 in microperiod 4. Both are substitutes for each other and disjunctive. Thus, for example, resource 3 cannot be used in parallel on both lines and another resource is used for line 2. Setting up both lines in parallel is not possible because disjunctive resource 6 is necessary for both of them. Also note that the minimum lotsize on line 2 is ensured in the second microperiod after the setup operation [c.f. constraint (9)].
6.5 A scenario requiring continuous setups
The last scenario necessitates continuous setup times. Besides the following changes all parameters remain the same as before. Demand occurs only in the second macroperiod: 10 units of product 1 and 5 units of product 2. The setup times are redefined: Each setup on line 1 lasts 3 time units and each setup on line 2 lasts 11 time units. Only one cumulative resource with a capacity of 10 units per macroperiod is considered. To produce one unit of product 1 or 2 one unit of the cumulative resource is necessary. The resulting production plan is shown in Fig. 10.
Production plan with cumulative resources and a continuous setup
Obviously, it is impossible to produce all products in macroperiod 2. The limited availability of the cumulative resource is the reason for this. Thus, 5 units of product 1 are produced in macroperiod 1 and stored until macroperiod 2. As intended, on line 2, there is a setup which continues over three microperiods and even exceeds a macroperiod boundary.
7 Summary and outlook
A mixed-integer, linear programming model for single-stage, simultaneous lotsizing and scheduling considering secondary resources (SRs) has been presented. In this field of research, besides the limited capacity of the primary resources (several parallel production lines of a single stage of production) also the limited availability of further (“secondary”), scarce resources like setup tools, setup operators or raw materials has to be respected.
A comprehensive literature research has revealed that most of the existing SR models are tailored to specific practical applications. It has also helped to develop a classification scheme for SRs, which comprises four different types of resources: disjunctive resources with and without substitutes and cumulative resources with and without substitutes. While disjunctive SRs can only serve a single production line at a single point in time and can be used several times consecutively (like setup tools), cumulative SRs can serve several production lines simultaneously and can be consumed only once (e.g., raw materials). Substitutability distinguishes whether only a single type of SR or several alternative types of SRs could be applied for a certain setup or production process.
The developed model is based on the general lotsizing and scheduling problem for parallel production lines (GLSPPL) and can represent general situations which combine all four types of SRs. Synchronization of SRs is realized using a common time structure on all parallel production lines. Substitutes for different skills and properties of SRs are incorporated using substitute sets. Additional index sets define which skills and properties are necessary to perform a certain process.
The major advantage of the model is that it unifies nearly all SR-constraints and SR-applications found in the literature within a single formulation. This formulation still remains compact since features, which were unnecessary for a certain application, could easily be left out by omitting the corresponding constraints and variables. Some features, which have not been dealt with in science so far but are of practical relevance, can also be incorporated. Examples are cumulative SRs with substitutes or the ability to refine the modeling of changeovers by distinguishing between dismounting, cleaning and mounting. Such an approach allows to construct more flexible and thus more realistic schedules.
Some examples have been presented which demonstrate the applicability of the new model. However, extensive numerical tests on the computational performance of the new model have not been performed. This would have gone beyond the scope of a single publication. Thus, future research has to analyze and, where possible, improve the performance of the formulation, but mainly to design scalable solution heuristics for problem instances of industrial size. If these base on the new model, they promise to be more generally applicable than current SR heuristics are. Nevertheless, the already existing models and heuristics for specific applications, which are referred to in Sect. 2, may serve as benchmarks for comparison. Another challenge for future research is to extend the model for multiple stages of production.
Notes
This denomination has only later been introduced by Fleischmann (1990).
See also Copil (2016).
Using the same index sequence ji three times for \(z^{c}_{lji,s-1}\), \(z^{c}_{ljis}\) and \(z_{ljis}\) allows (10) to carry the information, which product had been produced last, over all microperiods of a continued setup.
We omit the index l of the production lines for ease of readability.
If a property o does only refer to some ingredient of the SRs, as for example the sugar content of orange and pineapple concentrate, a corresponding factor \(a_{on}\) can be introduced and (24) can be changed to \(\sum _{n \in \Xi _o} a_{on} x^{p}_{lns} \ge f^{p}_{jo}x_{ljs}\).
References
Almada-Lobo B, Klabjan D, Carravilla MA, Oliveira JF (2010) Multiple machine continuous setup lotsizing with sequence-dependent setups. Comput Optim Appl 47(3):529–552
Almeder C, Almada-Lobo B (2011) Synchronisation of scarce resources for a parallel machine lotsizing problem. Int J Prod Res 49(24):7315–7335
Anupindi R, Chopra S, Deshmukh SD, Van Mieghem JA, Zemel E (2014) Managing business process flows, 3rd edn. Pearson Education Limited, London
Balakrishnan A, Geunes J (2000) Requirements planning with substitutions: exploiting bill-of-materials flexibility in production planning. Manuf Serv Oper Manag 2(2):166–185
Camargo VCB, Toledo FMB, Almada-Lobo B (2012) Three time-based scale formulations for the two stage lot sizing and scheduling in process industries. J Oper Res Soc 63:1613–1630
Camargo VCB, Toledo FMB, Almada-Lobo B (2014) HOPS—hamming-oriented partition search for production planning in the spinning industry. Eur J Oper Res 234(1):266–277
Copil K (2016) Capacitated lot-sizing and scheduling with scarce setup resources. Books on Demand, Norderstedt
Copil K, Wörbelauer M, Meyr H, Tempelmeier H (2017) Simultaneous lotsizing and scheduling problems: a classification and review of models. OR Spectr 39(1):1–64
Dastidar SG, Nagi R (2005) Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs. Comput Oper Res 32(11):2987–3005
Drexl A, Haase K (1995) Proportional lotsizing and scheduling. Int J Prod Econ 40(1):73–87
Eppen GD, Martin RK (1987) Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper Res 35(6):832–848
Ferreira D, Morabito Neto R, Rangel S (2009) Solution approaches for the soft drink integrated production lot sizing and scheduling problem. Eur J Oper Res 196(2):697–706
Ferreira D, Morabito Neto R, Rangel S (2010) Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants. Comput Oper Res 37(4):684–691
Ferreira D, Clark AR, Almada-Lobo B, Morabito Neto R (2012) Single-stage formulations for synchronised two-stage lot sizing and scheduling in soft drink production. Int J Prod Econ 136(2):255–265
Figueira G, Santos MO, Almada-Lobo B (2013) A hybrid VNS approach for the short-term production planning and scheduling: a case study in the pulp and paper industry. Comput Oper Res 40(7):1804–1818
Fleischmann B (1990) The discrete lot-sizing and scheduling problem. Eur J Oper Res 44(3):337–348
Fleischmann B, Meyr H (1997) The general lotsizing and scheduling problem. OR Spectr 19(1):11–21
Furlan MM, Almada-Lobo B, Santos MO, Morabito Neto R (2015) Unequal individual genetic algorithm with intelligent diversification for the lot-scheduling problem in integrated mills using multiple-paper machines. Comput Oper Res 59:33–50
Geunes J (2003) Solving large-scale requirements planning problems with component substitution options. Comput Ind Eng 44(3):475–491
Göthe-Lundgren M, Lundgren JT, Persson JA (2002) An optimization model for refinery production scheduling. Int J Prod Econ 78(3):255–270
Haase K (1996) Capacitated lot-sizing with sequence dependent setup costs. OR Spectr 18(1):51–59
Hartmann S, Briskorn D (2010) A survey of variants and extensions of the resource-constrained project scheduling problem. Eur J Oper Res 207(1):1–14
Jans R, Degraeve Z (2004) An industrial extension of the discrete lot-sizing and scheduling problem. IIE Trans 36(1):47–58
Karmarkar US, Schrage L (1985) The deterministic dynamic product cycling problem. Oper Res 33(2):326–345
Kimms A, Drexl A (1998) Proportional lot sizing and scheduling: some extensions. Networks 32(2):85–101
Koçlar A, Süral H (2005) A note on “The general lot sizing and scheduling problem”. OR Spectr 27(1):145–146
Lasdon L, Terjung RC (1971) An efficient algorithm for multi-item scheduling. Oper Res 19(4):946–969
Mac Cawley AF (2014) The international wine supply chain: challenges from bottling to the glass. Ph.D. thesis, Georgia Institute of Technology
Maldonado M, Rangel S, Ferreira D (2014) A study of different subsequence elimination strategies for the soft drink production planning. J Appl Res Technol 12(4):631–641
Meyr H (2002) Simultaneous lotsizing and scheduling on parallel machines. Eur J Oper Res 139(2):277–292
Meyr H (2004) Simultane Losgrößen- und Reihenfolgeplanung bei mehrstufiger kontinuierlicher Fertigung. Zeitschrift für Betriebswirtschaft 74(6):585–610
Meyr H, Mann M (2013) A decomposition approach for the general lotsizing and scheduling problem for parallel production lines. Eur J Oper Res 229(3):718–731
Persson JA, Göthe-Lundgren M, Lundgren JT, Gendron B (2004) A tabu search heuristic for scheduling the production processes at an oil refinery. Int J Prod Res 42(3):445–471
Santos MO, Almada-Lobo B (2012) Integrated pulp and paper mill planning and scheduling. Comput Ind Eng 63(1):1–12
Seeanner F (2013) Multi-stage simultaneous lot-sizing and scheduling—planning of flow lines with shifting bottlenecks. Produktion und Logistik. Springer Gabler, Wiesbaden
Seeanner F, Meyr H (2013) Multi-stage simultaneous lot-sizing and scheduling for flow line production. OR Spectr 35(1):33–73
Seeanner F, Almada-Lobo B, Meyr H (2013) Combining the principles of variable neighborhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems. Comput Oper Res 40(1):303–317
Suerie C (2005) Time continuity in discrete time models: new approaches for production planning in process industries. Lecture notes in economics and mathematical systems. Springer, Berlin
Tempelmeier H, Buschkühl L (2008) Dynamic multi-machine lotsizing and sequencing with simultaneous scheduling of a common setup resource. Int J Prod Econ 113(1):401–412
Tempelmeier H, Copil K (2016) Capacitated lot sizing with parallel machines, sequence-dependent setups and a common setup operator. OR Spectr 38(4):819–847
Toledo CFM, Arantes MdS, de Oliveira RRR, Almada-Lobo B (2013) Glass container production scheduling through hybrid multi-population based evolutionary algorithm. Appl Soft Comput 13(3):1352–1364
Acknowledgements
We thank the anonymous reviewers and area editor for their helpful comments. The third author was partially funded by ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme, and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project SAICTPAC/0034/2015-POCI-01- 0145-FEDER-016418.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wörbelauer, M., Meyr, H. & Almada-Lobo, B. Simultaneous lotsizing and scheduling considering secondary resources: a general model, literature review and classification. OR Spectrum 41, 1–43 (2019). https://doi.org/10.1007/s00291-018-0536-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-018-0536-0