There are a lot of scheduling problems in litterature, such as single machine problems, Flow-shops, and variants. We are here focusing on another one, namely the Job-shop. The Job-shop is a model of industrial problems that can be encountered in multiple pathways workshops. By « multiple pathways », it must be understood that each product has its own routing in the system, and all of them will not undergo the same operations. If products have different process plannings and must be treated by mutualized machines/units, then it is probably a Job-shop like production system. For instance, a product may undergo an operation on machine/workshop 1 first and on machine/workshop 2 after, whereas another product will start on machine/workshop 4 and then on machine/workshop 1. A drawing of a shop floor where each product must be treated by all machines/workshops is given below:
Obviously, all production systems do not look like the one presented above. However, it is common to have process plannings where some machines are mutualized. In the research litterature, this problem contains various constraints, the main ones being:
- Every Job (product) is available at the beginning of the scheduling process.
- Each operation must spend a known duration on each machine.
- The machining sequence (the order in which products are processed on the machines) is (usually) not the same for each product.
- A machine can handle only one product at a time.
- A product cannot be treated on more than one machine at a time.
- An operation on a machine can begin only if the previous operations in the routing are complete, and if the machine is available (stocks are neglected)
The purpose of such a problem is to find the best sequence of operations on the machines, providing the starting and ending dates of each operations, in order to minimize a given criterion, which is often (academically) the total duration required for processing all operations, also called « makespan ». Usually, the proposed schedule is represented as a Gantt chart, which can look like this:
The makespan is not the only objective in the litterature since other ones exist, such as (not exhaustive) minimization of the number of late jobs, or the total tardiness of jobs. In this last point, each job has a due date which must be respected or some penalties could be applied. However, if time oriented criteria are prevalent, they are generally not environmentally friendly, as we will talk on another post.
Actually, the Job-shop problem has many extensions. These extensions consist in adding additional constraints depending on case studies and industrial expectations. For instance, an extra constraint can be to respect durations that must not be overtaken between the end of an operation and the start of the next one in the processing order. This constraint is named « Time-Lags » and is the subject of another post. A lot of studies are conducted on particular cases of classical scheduling problems.
Should also be mentionned the setup times, the energy constraints, lot sizing issues, and other approaches dealing with stochasticity (where some disturbances on the production systems - such as machine failures, uncertain processing times, random job arrivals, ... - should be dealt with). Also, a lot of Flexible Manufacturing Systems can be studied as they often rely on Job-shop problems.
If you want to know more about the Job-shop problem, a not so recent, yet still valuable, state of the art presenting the Job-shop problem can be found in the work of Jain and Meeran (1999 - Deterministic Job-shop scheduling: Past, present and future. European Journal of Operations Research)