What constraints should be taken into account at the scheduling stage?
Scheduling in the broad sense aims to allocate resources to tasks and define the start date of each task. The 2 fundamental concepts are therefore:
- Tasks or events: these are operations requiring resources and having a certain duration
- Resources: machines, raw materials, etc. with known availability over time
A first typology of scheduling problems arises from that of each of these 2 basic notions:
- Resources can be renewable (equipment) or consumable (materials)
- Tasks may or may not be splittable. Splittable tasks are found in continuous or semi-continuous process industries
Added to this are the types of constraints specific to the manufacturing process, including:
- Constraints on availability of resources or demands to be satisfied depending on time
- Constraints relating to tasks: precedence, disjunctive constraints (non-overlap), etc.
- Others: transit time, limits on outstanding amounts, etc.
Finally, the type of market determines the nature of the scheduling process, depending on whether it involves requests known in advance (static) or whether it is necessary to respond to requests that arrive in real time (dynamic).
Three families of processes respond to distinct resolution approaches
By combining these different classification criteria, we can identify the 3 main families of processes and the resolution approaches appropriate to each:
- Continuous processes which are characterized by the presence of consumable resources and splittable tasks, as well as limits on stocks. The appropriate approach in this case is mathematical programming when the size of the problem allows it, and flow simulation for large cases (trial and error approaches)
- Manufacturing industries, mechanical workshops, etc. which are characterized by renewable resources, non-splitable tasks and constraints on the sequencing of tasks. In this category, we find so-called flow-shop problems (products must pass through a fixed sequence of machines, such as assembly lines) and job-shop problems (where each part must visit a specific sequence of machines). The appropriate approach in these cases is constraint programming for very constrained cases, or metaheuristics (less constrained cases)
- Semi-continuous processes where there is operation in campaigns or batches and which combine aspects of the two previous families, including the following:
- Existence of consumable resources
- Limits on outstanding amounts
- Tasks that can be split but subject to penalty, in the sense that batch size is a variable, but where campaign changeover costs require finding a compromise between batch size and the quantity of immobilized inventory
- Series change penalties depend on the nature and order of the batches
- These problems relate to local search approaches and metaheuristics: simulated annealing, evolutionary algorithms, often combined with priority rules specific to each industry.
