Planning a reservation (not a restaurant) with python

Question

I am writing a python application that uses OpenStack to provide students with access to a limited number of virtual machines.

Students can place reservations both now and in the future.

I need to limit the number of virtual machines scheduled at any time to X, while still allowing students to reserve vms if slots / reservations are available.

The backup objects are as follows (sqlalchemy). I would like to know the start time and duration of the requested reservation, after which I need to go through the existing reservations and see if there are too many reservations in the requested time period. The * _job fields are the names of the APScheduler jobs.

class Reservation(Entity): student = ManyToOne('Student', required=True) class_id = ManyToOne('Class', required=True) image = ManyToOne('Image', required=True) # openstack image id filled in once the instance is started instance_id = Field(UnicodeText) # apscheduler jobs stop_instance_job = Field(UnicodeText) start_instance_job = Field(UnicodeText) warn_reservation_ending_job = Field(UnicodeText) check_instance_job = Field(UnicodeText) 

Any pointers to where to look for examples of scheduling algorithms or something like that? I don’t even know what to look for ...

Thanks.

Answer 1

You should look at Grid-based Schedulers. Typically, the schedulers do not know the true execution time (or the time the resources were used), and complex heuristics are used to determine how long the problem will run (see Such heuristics in the grid scheduler at: Download in PDF Description of grid-based planning ). A simpler basic grid approach to represent the workload over time is likely to satisfy your needs. Python does not have any amazing libraries of grid objects that I know of (I used to implement several in C ++ and Python, although they are not too complicated). You should look at the numpy package for an easier interpretation of multidimensional objects - which can easily emulate or implement meshes.

Msw mentioned Dijkstra Banker Algorithm, which is a form of job scheduling - however, your problem cares about the future state more than the current state, and you can accurately predict (know the true value) the time of the task. Thus, there will be enough T (timesteps) for N (the number of resources - maybe only 1) by the network M (maximum reservation of resources), which you fill out, since tasks are registered. Determining whether a particular task can be scheduled in a specific time interval is to check O (task_length * M) in the grid unit (start, stop) x (required_resources) x (1, M) for an empty slot.

Finding the right place for a specific task (choosing a start time) is a more difficult task and will be achieved using a modified Dijkstra algorithm or any standard scheduler (msw comment is more useful for this task than for a time interval health check). Please note: most of the content of the scheduler on the Internet depends on the planning of the OS processes, which cares more about the type of operation (input / output or not) and about fines for a longer period than expected than about the abstract use of resources. Thus, Google planners' search queries often provide you with the realities of the Linux scheduler, rather than methods for arbitrary data. Try to find the shortest task schedulers, which are often simpler and less dependent on the tasks of the OS when explaining.