Abstract
Batch flow shops model systems that process a variety of job types using a fixed infrastructure. This model has applications in several areas including chemical manufacturing, building construction, and assembly lines. Since the throughput of such systems depends, often strongly, on the sequence in which they produce various products, scheduling these systems becomes a problem with very practical consequences. Nevertheless, optimally scheduling these systems is NP-complete. This paper demonstrates that batch flow shops can be represented as a particular kind of heap model in the max-plus algebra. These models are shown to belong to a special class of linear systems that are globally stable over finite input sequences, indicating that information about past states is forgotten in finite time. This fact motivates a new solution method to the scheduling problem by optimally solving scheduling problems on finite-memory approximations of the original system. Error in solutions for these “t-step” approximations is bounded and monotonically improving with increasing model complexity, eventually becoming zero when the complexity of the approximation reaches the complexity of the original system.
Similar content being viewed by others
References
Ahmadi J H, Ahmadi R H, Dasu S, Tang C S (1992) Batching and scheduling jobs on batch and discrete processors. Oper Res 39(4):750–763
Beck C, Doyle J, Glover K (1996) Model reduction of multidimensional and uncertain systems. IEEE Trans Autom Control 41(10):1466–1477
Baccelli F, Cohen G, Olsder G J, Quadrat J P (1992) Synchronization and linearity. Wiley
Bemporad A (2003) Multiparametric nonlinear integer programming and explicit quantized optimal control. In: Proceedings 42nd IEEE conf decis control. pp 3167–3172
Blömer F, Günther H (1998) Scheduling of a mutli-product batch process in the chemical industry. Comput Ind 36:245–259
Boccadoro M, Valigi P (2003) A modelling approach for the dynamic scheduling problem of manufacturing systems with non negligible setup times and finite buffers. In: Proceedings 42nd IEEE conf decis control
Bouquard J L, Lenté C, Billaut J C (2006) Application of an optimization problem in max-plus algebra to scheduling problems. Discret Appl Math 154(15):2064–2079
Bouquard JL, Lenté C, Billaut JC (2006) Two-machine flow shop scheduling problems with minimal and maximal delays. 4OR: A Q J Oper Res 4:15–28
Cheng T, Ng C, Yuan J, Liu Z (2004) Single machine parallel batch scheduling subject to precedence constraints. Nav Res Logist 51:949–958
Cohen G, Dubois D, Quadrat J P, Viot M (1985) A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Trans Autom Control AC-30(3):210–220
Corona D, Giua A, Seatzu C (2005) Quantized optimal control of discrete-time systems. In: 10th IEEE conference of ETFA
Deng X, Feng H, Li G, Lui G (2002) A PTAS for minimizing total completion time of bounded batch scheduling. Int J Found Comput Sci 13(6):817–827
Dobson G, Nambimadom R S (2001) The batch loading and scheduling problem. Oper Res 49(1):52–65
Dullerud G, Paganini F (2000) A course in robust control theory: a convex approach. Appl Math. Springer
Dupont L, Dhaenens-Flipo C (2002) Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Comput Oper Res 29(7):807–819
French S (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop. Math Appl. Ellis Horwood Limited
Gaubert S, Mairesse J (1999) Modeling and analysis of timed petri nets using heaps of pieces. IEEE Trans Autom Control 44(4):683–697
Glass C, Potts C, Strusevich V (2001) Scheduling batches with sequential job processing for two-machine flow and open shops. INFORMS J Comput 13(2):120–137. Spring
Gupta J N D (1986) Flowshop schedules with sequence dependent setup times. J Oper Res Soc Jpn 29(3):206–219
Hall N, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510–525
Heidergott B, Olsder G J, van der Woude J (2006) Max plus at work: modeling and analysis of synchronized systems: a course on max-plus algebra and its applications princeton series in applied mathematics. Princeton University Press
Hochbaum D, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45(6):874–885
Jordan C, Drexl A (1998) Discrete lotsizing and scheduling by batch sequencing. Manag Sci 44(5):698–713
Kondili E, Pantelides C C, Sargent R W H (1993) A general algorithm for short-term scheduling of batch operations - I. MILP formulation. Comput Chem Eng 17(2):211–227
Lin B, Cheng T (2001) Batch scheduling in the no-wait two-machine flowshop to minimize the makespan. Comput Oper Res 28:613–624
López-Mellado E, Villanueva-Paredes N, Almeyda-Canepa H (2005) Modelling of batch production systems using Petri nets with dynamic tokens. Comput Oper Res 67(6):541–558
Parker R G (1995) Deterministic scheduling theory. Chapman and Hall
Pinedo M L (2005) Planning and scheduling in manufacturing and services. Springer series in operations research. Springer Science+Business Media Inc.
Reddi S, Ramamoorthy C (1972) On the flow-shop sequencing problem with no wait in process. Oper Res Q 23(3):323–331
Rich S H, Prokopakis G J (1986) Scheduling and sequencing of batch operations in a multipurpose plant. Ind Eng Chem Process Des Dev 25:979–988
Riera D, Narciso M, Benqlilou C (2005) A petri nets-based scheduling methodology for multipurpose batch plants. Simul 81:613–623
Roe B, Papageorgiou L, Shah N (2005) A hybrid MILP/CLP algorithm for multipurpose batch process scheduling. Comput Chem Eng 29:1277–1291
Sand G, Engell S (2004) Modeling and solving real-time scheduling problems by stochastic integer programming. Comput Chem Eng 28:1087–1103
Sanmartí E, Puigjaner L, Holczinger T, Friedler F (2002) Combinatorial framework for effective scheduling of multipurpose batch plants. AIChE J 48(11):2557–2570
Savkin A (2003) Optimal distributed real-time scheduling of flexible manufacturing networks modeled as hybrid dynamical systems. In: Proceedings IEEE conf decis control
Su R, Woeginger G (2011) String execution time for finite languages: max is easy, min is hard. Autom 47(10):2326–2329
Van den Boom T J J, De Schutter B (2006) Modelling and control of discrete event systems using switching max-plus-linear systems. Control Eng Pract 14(10):1199–1211
van Eekelen J, Lefeber E, Rooda J (2006) Feedback control of 2-product server with setups and bounded buffers. In: Proceedings IEEE American control conference
van Eekelen J, Lefeber E, Roset B, Rooda J (2005) Control of manufacturing systems using state feedback and linear programming. In: Proceedings of IEEW conference on decision and control
Vanderbei R J (2001) Linear programming: foundations and extensions, 2nd edn. Kluwer Academic Publishers
Weyerman W, Warnick S (2007) Monotonically improving error bounds for a sequence of approximations for makespan minimization of batch manufacturing systems. In: Proceedings of IEEE conference on decisions and control
Yajima T, Ito T, Hashizume S, Kurimoto H, Onogi K (2004) Control of batch processes based on hierarchical petri nets. IEICE Trans Fundam E87-A(11):2895–2904
Yurdakul M, Odrey N G (2004) Development of a new dioid algebraic model for manufacturing with the scheduling decision making capability. Robot Auton Syst:207–218
Acknowledgments
This work has been funded by generous contributions from the Department of Homeland Security (DHS) Science and Technology Directorate, Homeland Security Advanced Research Projects Agency (HSARPA), Cyber Security Division (DHS S&T/HSARPA/CSD), LRBAA 12-07 via contract number HSHQDC-13-C-B0052, as well as from contributions from AFRL FA8750-09-2-0219 and ATK Thiokol. All material in this paper represents the position and work of the authors and not necessarily that of the sponsors.
The authors would like to thank Professor Tyler Jarvis of the Mathematics Department at Brigham Young University for useful discussions during the early phase of this research. We also gratefully acknowledge the considerable work and suggestions of the anonymous reviewers which, in our opinion, contributed significantly to the readability and clarity of this work.
Author information
Authors and Affiliations
Corresponding author
Appendix: Proof of Theorem 1
Appendix: Proof of Theorem 1
Lemma 11
Given \(B \in \mathbb {R}_{\max }^{n \times n}\) that satisfies Eq. 7 and ( c, τ )(α), the matrix resulting from finitely many left multiplications of P i (k) and R i (k) for any i with B satisfies Eq. 7.
Proof
Let \(B \in \mathbb {R}_{\max }^{n \times n}\) that satisfies Eq. 7, (c, τ )(α), and i≤n be given. After a left multiply of P i (k), Eq. 7 is trivially satisfied. Suppose that i<n. Consider the product A=R i (k)⊗B. Because the only difference between A and B is in rows i and i+1, we want to show that a i j ≥a i,j+1 and a i+1,j ≥a i+1,j+1 for all j<n. We will consider two cases.
Suppose b i j ≥b i+1,j . Then a i j =b i j =a i+1,j . Because B satisfies (7) it follows that b i j ≥b i,j+1 and b i j ≥b i+1,j ≥b i+1,j+1. So a i j ≥a i,j+1 and a i+1,j ≥a i+1,j+1.
Suppose b i+1,j ≥b i j . We achieve the same result as the previous case in the same manner.
Thus, because B satisfies Eq. 7 after a left multiply of an arbitrary P i or R i , after a finite number of left multiplies, the resulting matrix will satisfy Eq. 7.
Lemma 12
Given \(B \in \mathbb {R}_{\max }^{n \times n}\) that satisfies Eq. 8 and ( c, τ )(α), the matrix resulting from finitely many left multiplications of P i (k) and R i (k) for any i with B satisfies Eq. 8.
Proof
Let \(B \in \mathbb {R}_{\max }^{n \times n}\) that satisfies Eq. 8, (c, τ )(α), and i≤n be given. Left multiplying B by P i adds the same number to every element of row i. As this does not change ξ i j for any j, the resulting matrix still satisfies Eq. 8. Now suppose that we left multiply B by R i for some i<n. The resulting matrix, A, has rows i and i+1 equal. We now have
We need now show that ξ i −1,j (A)≥ξ i j (A) and that ξ i+1,j (A)≥ξ i+2,j (A). We will handle each of four cases separately.
-
Suppose b i j ≥b i+1,j and b i,j+1≥b i+1,j+1. Then
$$\begin{array}{rcl} a_{ij} - a_{i,j+1} & = & b_{ij} - b_{i,j+1} \end{array}$$and
$$\begin{array}{rcl} a_{i+1,j} - a_{i+1,j+1} & = & b_{ij} - b_{i,j+1} \\ & \geq & b_{i+1,j} - b_{i+1,j+1}. \end{array}$$ -
Suppose b i j ≥b i+1,j and b i,j+1≤b i+1,j+1. Then
$$\begin{array}{rcl} a_{ij} - a_{i,j+1} & = &b_{ij} - b_{i+1,j+1} \\ & \leq & b_{ij} - b_{i,j+1} \\ \end{array} $$and
$$\begin{array}{rcl} a_{i+1,j} - a_{i+1,j+1} & = & b_{ij} - b_{i+1,j+1} \\ & \geq & b_{i+1,j} - b_{i+1,j+1}. \end{array}$$ -
Suppose b i j ≤b i+1,j and b i,j+1≥b i+1,j+1. But then
$$\begin{array}{rcl} b_{ij} - b_{i,j+1} & \leq & b_{i+1,j} - b_{i+1,j+1} \end{array} $$which violates the assumption on B, so this case is not possible.
-
Finally, suppose b i j ≤b i+1,j and b i,j+1≤b i+1,j+1. Then
$$\begin{array}{rcl} a_{ij} - a_{i,j+1}& = &b_{i+1,j} - b_{i+1,j+1} \\ & \leq & b_{i,j} - b_{i+1,j} \end{array} $$and
$$\begin{array}{rcl} a_{i+1,j} - a_{i+1,j+1}& = &b_{i+1,j} - b_{i+1,j+1}. \end{array} $$
We have shown that in any case, ξ i j (A)≤ξ i j (B) and ξ i+1,j (A)≥ξ i+1,j (B). For any l≠i and l≠i+1, ξ l j (A)=ξ l j (B) for all j. Thus, ξ i −1,j (A)≥ξ i j (A)=ξ i+1,j (A)≥ξ i+2,j (A), so Eq. 8 is satisfied after a left multiply of R i .
Because we have shown that the resulting matrix after a left multiply of arbitrary P i or arbitrary R i satisfies Eq. 8, it follows that Eq. 8 is satisfied after a finite number of left multiplies.
We are now ready to prove the main theorem.
Proof of Theorem 1
Let (c, τ )(α) be given. The algorithm for constructing A(α) begins with I m a x . The block of I m a x consisting of i 11 is trivially in \(\mathcal {M}^n\). Thus we know by the Lemmata 11 and 12 that this block satisfies Eq. 7 and Eq. 8 throughout the algorithm. We will show by induction that by the end of the algorithm the entire matrix satisfies both of these. Suppose that at the p th stage of the algorithm, the block from b 11 to b k k of the current matrix B satisfies Eq. 7 and Eq. 8 and the remainder of the matrix consists of 𝜖 off the diagonal and e on the diagonal. Consider now C=R k ⊗B, we can suppose without loss of generality that this is the next operation the algorithm performs. Row k+1 of C is equal to row k of C, with the only difference between row k of C and row k of B being that c k,k+1=e and b k,k+1=𝜖. Therefore ξ i k (C)=∞ for i<k and ξ k k (C)<∞, so the block from c 11 to c k+1,k+1 satisfies (8). Also, because we must multiply by P k before R k , c k k >c k,k+1=0, so the block from c 11 to c k+1,k+1 satisfies Eq. 7. The remaining rows and columns of C consist of 𝜖 off the diagonal and e on the diagonal. Therefore, by induction, A must satisfy Eq. 7 and Eq. 8.
It remains to be shown that A satisfies Eq. 6 and Eq. 9. By the algorithm, we can write,
where B n −j is some intermediate matrix sum. This sequence of R i ’s shows that the 0 entries on the diagonal or I m a x will be cascaded down through the columns of the matrix, it will also ensure that the entries just above the diagonal are greater than −∞, and we see that A satisfies Eq. 9.
For Eq. 6, consider the last multiplication of P i for some i. This is necessarily followed by a multiplication of R i , at this point the resulting matrix, C, has c i j =c i+1,j . This matrix is necessarily multiplied by P i+1 before another R i or P i ; the resulting matrix, which we will call D, has d i j ≤d i+1,j , at this point we know a i j =d i j and a i+1,j ≥d i+1,j , so A must satisfy Eq. 6.
Rights and permissions
About this article
Cite this article
Weyerman, W.S., Rai, A. & Warnick, S. Model approximation for batch flow shop scheduling with fixed batch sizes. Discrete Event Dyn Syst 25, 497–529 (2015). https://doi.org/10.1007/s10626-014-0195-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-014-0195-5