In scheduling problems, one usually has different options as objective functions (makespan, tardiness, etc). However, for any such type of scheduling problem one can consider an online version of it on which new jobs are arriving to be processed at random times. This seems more natural in practice. I was thus wondering how are practitioners modeling this in industry and what strategies are they following to solve it.
My first thought was to follow the workflow:
- Get data on jobs today and solve the associated (offline)problem to this data
- Start processing jobs according to the computed schedule
- While jobs are being processed, record the incoming jobs, but keep them hidden from the solver
- After a fixed short period of time (usually before the makespan of the precomputed schedule) show these additional jobs to the solver and ask it to solve a new problem with these jobs plus the jobs that are still not processed from the previous schedule at that point in time.
- Go to step 2.
However, this procedure seems very naive because in theory old orders can be always pushed to the end and never be processed (for example, if we are minimizing the total number of delayed orders and you have a big order that will take a lot of time and delay many orders if processed). So, what objective should we aim to minimize in this case? Can you please provide a reference I could checkout on this topic?
