×

Model approximation for batch flow shop scheduling with fixed batch sizes. (English) Zbl 1327.90078

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
15A80 Max-plus and related algebras
65Y20 Complexity and performance of numerical algorithms

Software:

LPbook
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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 · Zbl 0758.90042 · doi:10.1287/opre.40.4.750
[2] Beck C, Doyle J, Glover K (1996) Model reduction of multidimensional and uncertain systems. IEEE Trans Autom Control 41(10):1466-1477 · Zbl 0862.93009 · doi:10.1109/9.539427
[3] Baccelli F, Cohen G, Olsder G J, Quadrat J P (1992) Synchronization and linearity. Wiley · Zbl 0824.93003
[4] Bemporad A (2003) Multiparametric nonlinear integer programming and explicit quantized optimal control. In: Proceedings 42nd IEEE conf decis control. pp 3167-3172 · Zbl 1228.93005
[5] Blömer F, Günther H (1998) Scheduling of a mutli-product batch process in the chemical industry. Comput Ind 36:245-259 · doi:10.1016/S0166-3615(98)00075-X
[6] 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
[7] 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 · Zbl 1111.90038 · doi:10.1016/j.dam.2005.04.011
[8] 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 · Zbl 1125.90350 · doi:10.1007/s10288-005-0069-7
[9] Cheng T, Ng C, Yuan J, Liu Z (2004) Single machine parallel batch scheduling subject to precedence constraints. Nav Res Logist 51:949-958 · Zbl 1055.90034 · doi:10.1002/nav.20035
[10] 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 · Zbl 0557.93005 · doi:10.1109/TAC.1985.1103925
[11] Corona D, Giua A, Seatzu C (2005) Quantized optimal control of discrete-time systems. In: 10th IEEE conference of ETFA · Zbl 1071.93028
[12] 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 · Zbl 1067.68178 · doi:10.1142/S0129054102001473
[13] Dobson G, Nambimadom R S (2001) The batch loading and scheduling problem. Oper Res 49(1):52-65 · Zbl 1163.90486 · doi:10.1287/opre.49.1.52.11189
[14] Dullerud G, Paganini F (2000) A course in robust control theory: a convex approach. Appl Math. Springer · Zbl 0939.93001
[15] 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 · Zbl 0995.90081 · doi:10.1016/S0305-0548(00)00078-2
[16] French S (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop. Math Appl. Ellis Horwood Limited · Zbl 0479.90037
[17] Gaubert S, Mairesse J (1999) Modeling and analysis of timed petri nets using heaps of pieces. IEEE Trans Autom Control 44(4):683-697 · Zbl 0955.68082 · doi:10.1109/9.754807
[18] 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 · Zbl 1238.90064 · doi:10.1287/ijoc.13.2.120.10521
[19] Gupta J N D (1986) Flowshop schedules with sequence dependent setup times. J Oper Res Soc Jpn 29(3):206-219 · Zbl 0625.90042
[20] Hall N, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510-525 · Zbl 0864.90060 · doi:10.1287/opre.44.3.510
[21] 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 · Zbl 1130.93003
[22] Hochbaum D, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45(6):874-885 · Zbl 0895.90116 · doi:10.1287/opre.45.6.874
[23] Jordan C, Drexl A (1998) Discrete lotsizing and scheduling by batch sequencing. Manag Sci 44(5):698-713 · Zbl 0989.90065 · doi:10.1287/mnsc.44.5.698
[24] 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 · doi:10.1016/0098-1354(93)80015-F
[25] Lin B, Cheng T (2001) Batch scheduling in the no-wait two-machine flowshop to minimize the makespan. Comput Oper Res 28:613-624 · Zbl 0990.90044 · doi:10.1016/S0305-0548(99)00138-0
[26] 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 · Zbl 1066.90019
[27] Parker R G (1995) Deterministic scheduling theory. Chapman and Hall · Zbl 0873.90055
[28] Pinedo M L (2005) Planning and scheduling in manufacturing and services. Springer series in operations research. Springer Science+Business Media Inc. · Zbl 0758.90042
[29] Reddi S, Ramamoorthy C (1972) On the flow-shop sequencing problem with no wait in process. Oper Res Q 23(3):323-331 · Zbl 0238.90080 · doi:10.1057/jors.1972.52
[30] 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 · doi:10.1021/i200035a024
[31] Riera D, Narciso M, Benqlilou C (2005) A petri nets-based scheduling methodology for multipurpose batch plants. Simul 81:613-623 · doi:10.1177/0037549705061649
[32] Roe B, Papageorgiou L, Shah N (2005) A hybrid MILP/CLP algorithm for multipurpose batch process scheduling. Comput Chem Eng 29:1277-1291 · doi:10.1016/j.compchemeng.2005.02.024
[33] Sand G, Engell S (2004) Modeling and solving real-time scheduling problems by stochastic integer programming. Comput Chem Eng 28:1087-1103 · doi:10.1016/j.compchemeng.2003.09.009
[34] Sanmartí E, Puigjaner L, Holczinger T, Friedler F (2002) Combinatorial framework for effective scheduling of multipurpose batch plants. AIChE J 48(11):2557-2570 · doi:10.1002/aic.690481115
[35] Savkin A (2003) Optimal distributed real-time scheduling of flexible manufacturing networks modeled as hybrid dynamical systems. In: Proceedings IEEE conf decis control · Zbl 1067.68178
[36] Su R, Woeginger G (2011) String execution time for finite languages: max is easy, min is hard. Autom 47(10):2326-2329 · Zbl 1228.93005 · doi:10.1016/j.automatica.2011.06.024
[37] 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 · doi:10.1016/j.conengprac.2006.02.006
[38] 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
[39] 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 · Zbl 1228.93005
[40] Vanderbei R J (2001) Linear programming: foundations and extensions, 2nd edn. Kluwer Academic Publishers · Zbl 1043.90002
[41] 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
[42] 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
[43] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.