Model predictive scheduling of semi-cyclic discrete-event systems using switching max-plus linear models and dynamic gra
- PDF / 1,006,433 Bytes
- 35 Pages / 439.642 x 666.49 pts Page_size
- 13 Downloads / 167 Views
Model predictive scheduling of semi-cyclic discrete-event systems using switching max-plus linear models and dynamic graphs Ton J. J. van den Boom1 · Marenne van den Muijsenberg1 · Bart De Schutter1 Received: 13 July 2018 / Accepted: 12 April 2020 / © The Author(s) 2020
Abstract In this paper we discuss scheduling of semi-cyclic discrete-event systems, for which the set of operations may vary over a limited set of possible sequences of operations. We introduce a unified modeling framework in which different types of semi-cyclic discrete-event systems can be described by switching max-plus linear (SMPL) models. We use a dynamic graph to visualize the evolution of an SMPL system over a certain period in a graphical way and to describe the order relations of the system events. We show that the dynamic graph can be used to analyse the structural properties of the system. In general the model predictive scheduling design problem for SMPL systems can be recast as a mixed integer linear programming (MILP) problem. In order to reduce the number of optimization parameters we introduce a novel reparametrization of the MILP problem. This may lead to a decrease in computational complexity. Keywords Switching max-plus linear systems · Model predictive scheduling · Mixed integer linear programming
1 Introduction Scheduling is the process of deciding how to allocate a set of jobs to limited resources over time in such a way that one or more objectives are optimized (Leung 2004; Pinedo 2001). Here, a job is a sequence of operations according to a recipe that specifies a partial ordering among these operations, and resources are the equipment units where operations can take place. In a typical scheduling problem, resources are scarce and constrained in various ways (e.g., in the capacity of resources or the order of activities that can be performed on them), and one is looking for a schedule of the activities that both satisfies the constraints and is optimal according to some criterion (e.g., the length of the schedule) (Fromherz 2001). A lot
Ton J.J. van den Boom
[email protected] 1
Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands
Discrete Event Dynamic Systems
of research on scheduling has been done since the original work of Johnson (1954). Several books already presented general surveys for these problems such as Blazewicz et al. (2001), Brucker (2001), and Pinedo (2001) for some recent ones. In scheduling three basic types of control decisions play a major role, namely routing, ordering, and synchronization. Routing decides how a job follows a sequence of resources. Usually a job follows a predetermined route through the system (Johnson 1954). Sometimes there are alternative routes and the routing for each job has to be determined. Once the routes of the jobs have been fixed, conflicts may occur when multiple jobs need to be operated at the same resource. This means we have determine the ordering of concurring jobs in resources. Often job synchronization takes pl
Data Loading...
