1
$\begingroup$

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:

  1. Get data on jobs today and solve the associated (offline)problem to this data
  2. Start processing jobs according to the computed schedule
  3. While jobs are being processed, record the incoming jobs, but keep them hidden from the solver
  4. 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.
  5. 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?

$\endgroup$

2 Answers 2

1
$\begingroup$

Disclaimer: I'm not a practitioner, so I don't know if any of the relevant academic literature is actually, well, relevant. That said, I think you might want to look at work on "rolling horizon" scheduling. In particular, this question on OR SE and its answers are pertinent.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer! Second time this week :) $\endgroup$
    – John D
    Mar 15, 2023 at 15:38
1
$\begingroup$

Take a look into Real-time planning and Non-disruptive replanning. See my video.

$\endgroup$
1
  • $\begingroup$ Many thanks for the answer! $\endgroup$
    – John D
    Mar 15, 2023 at 15:38

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .