×

zbMATH — the first resource for mathematics

Throughput-optimal sequences for cyclically operated plants. (English) Zbl 1176.90232
Summary: In this paper, we present a method to determine globally optimal schedules for cyclically operated plants where activities have to be scheduled on limited resources. In cyclic operation, a large number of entities is processed in an identical time scheme. For strictly cyclic operation, where the time offset between entities is also identical for all entities, the objective of maximizing throughput is equivalent to the minimization of the cycle time. The resulting scheduling problem is solved by deriving a mixed integer optimization problem from a discrete event model. The model includes timing constraints as well as open sequence decisions for the activities on the resources. In an extension, hierarchical nesting of cycles is considered, which often allows for schedules with improved throughput. The method is motivated by the application to high throughput screening plants, where a specific combination of requirements has to be obeyed (e.g. revisited resources, absence of buffers, or time window constraints).

MSC:
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
93C65 Discrete event control/observation systems
Software:
CPLEX
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alle A, Papageorgiou L, Pinto J (2004) A mathematical programming approach for cyclic production and cleaning scheduling of multistage continuous plants. Comput Chem Eng 28(1–2):3–15 · doi:10.1016/S0098-1354(03)00171-6
[2] Bertsimas D, Weismantel R (2005) Optimization over integers. Dynamic Ideas, Belmont
[3] Brucker P (2004) Scheduling algorithms. Springer · Zbl 1060.90034
[4] Chen H, Chu C, Proth J-M (1998) Cyclic scheduling of a hoist with time window constraints. IEEE Trans Robot Autom 14(1):144–152 · doi:10.1109/70.660860
[5] Crama Y, Kats V, van de Klundert J, Levner E (2000) Cyclic scheduling in robotic flowshops. Ann Oper Res 96:97–124 · Zbl 0997.90032 · doi:10.1023/A:1018995317468
[6] Hall N, Lee T-E, Posner M (2002) The complexity of cyclic shop scheduling problems. J Sched 5(4):307–327 · Zbl 1009.90048 · doi:10.1002/jos.100
[7] ILOG (2006) ILOG CPLEX. http://www.ilog.com/products/cplex/
[8] Karimi I, Tan Z, Bhushan S (2004) An improved formulation for scheduling an automated wet-etch station. Comput Chem Eng 29(1):217–224 · doi:10.1016/j.compchemeng.2004.07.007
[9] Lee T-E (2000) Stable earliest starting schedules for cyclic job shops: a linear system approach. Int J Flex Manuf Syst 12(1):59–80 · doi:10.1023/A:1008123115577
[10] Lee T-E, Posner M (1997) Performance measures and schedules in periodic job shops. Oper Res 45(1):72–91 · Zbl 0892.90102 · doi:10.1287/opre.45.1.72
[11] Levner E, Kats V (1998) A parametric critical path problem and an application for cyclic scheduling. Discrete Appl Math 87(1–3):149–158 · Zbl 0906.68108 · doi:10.1016/S0166-218X(98)00054-7
[12] Levner E, Kats V, Levit V (1997) An improved algorithm for cyclic flowshop scheduling in a robotic cell. Eur J Oper Res 97(3):500–508 · Zbl 0919.90088 · doi:10.1016/S0377-2217(96)00272-X
[13] Mayer E (2007) Globally optimal schedules for cyclic systems with non-blocking specification and time window constraints. PhD Thesis, Fachgebiet Regelungssysteme, Technische Universität Berlin, Germany.
[14] Mayer E, Raisch J (2003) Throughput-optimal scheduling for cyclically repeated processes. MMAR2003–9th IEEE international conference on methods and models in automation and robotics. Miedzyzdroje, Poland, pp 871–876
[15] Mayer E, Raisch J (2004) Time-optimal scheduling for high throughput screening processes using cyclic discrete event models. MATCOM–Math Comput Simul 66(2–3):181–191 · Zbl 1048.90106 · doi:10.1016/j.matcom.2003.11.004
[16] Middendorf M, Timkovsky VG (2002) On scheduling cycle shops: classification, complexity and approximation. J Sched 5(2):135–169 · Zbl 1024.90041 · doi:10.1002/jos.95
[17] Murray C, Anderson C (1996) Scheduling software for high-throughput screening. Lab Robot Autom 8(5):295–305 · doi:10.1002/(SICI)1098-2728(1996)8:5<295::AID-LRA6>3.0.CO;2-W
[18] Odijk M (1996) A constraint generation algorithm for the construction of periodic railway timetables. Transp Res Part B–Methodol 30B(6):455–464 · doi:10.1016/0191-2615(96)00005-7
[19] Parker R (1995) Deterministic scheduling theory. Chapman & Hall · Zbl 0873.90055
[20] Pinedo M (1995) Scheduling: theory, algorithms, and systems. Prentice Hall · Zbl 1145.90393
[21] Pinto J, Grossmann I (1994) Optimal cyclic scheduling of multistage continuous multiproduct plants. Comput Chem Eng 18(9):797–816 · doi:10.1016/0098-1354(93)E0021-Z
[22] Pinto J, Grossmann I (1998) Assignment and sequencing models for the scheduling of process systems. Ann Oper Res 81:433–466 · Zbl 0911.90220 · doi:10.1023/A:1018929829086
[23] Roundy R (1992) Cyclic schedules for job shops with identical jobs. Math Oper Res 17(4):842–865 · Zbl 0770.90036 · doi:10.1287/moor.17.4.842
[24] Seo J-W, Lee T-E (2002) Steady-state analysis and scheduling of cyclic job shops with overtaking. Int J Flex Manuf Syst 14(4):291–318 · doi:10.1023/A:1020911406530
[25] Shah N, Pantelides C, Sargent R (1993) Optimal periodic scheduling of multipurpose batch plants. Ann Oper Res 42(1–4):193–228 · Zbl 0775.90219 · doi:10.1007/BF02023176
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.