Problem description

May 1, 2017 by ACADEMA

Job shop scheduling (JSS) is an optimization problem in computer science and operations research in which jobs are assigned to resources at particular times. The most basic version is as follows: We are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan. The makespan is the total length of the schedule (that is, when all the jobs have finished processing).

Example above: 2 working machines, 1 forklift, material for task 1 (j1) available later at the specific time, material for task 2 (j2) is available at the beginning, machine 1 is not available all the time, every task has different price per machine, production time differ, too.

The standard version of the problem is where you have n jobs J1, J2, ..., Jn. Within each job there is a set of operations O1, O2, ..., On which need to be processed in a specific order (known as Precedence constraints). Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop where each operation can be processed on any machine of a given set (the machines in the set are identical).

Constraints

Many variations of the problem exist, including the following:

• Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop)
• Machines can require a certain gap between jobs or no idle-time
• Machines can have sequence-dependent setups
• Objective function can be to minimize the makespan, the Lp norm, tardiness, maximum lateness etc. It can also be multi-objective optimization problem
• Jobs may have constraints, for example a job i needs to finish before job j can be started (depends on workflow). Also, the objective function can be multi-criteria.
• Set of jobs can relate to different set of machines
• Deterministic (fixed) processing times or probabilistic processing times

The formulation is defined as a specific set of soft constraints together with the weights associated with each of them. The JSS problem is formulated as a combinatorial optimization problem whose objective function is to minimize the weighted sum of penalty points.

Example

Example above: 24 working machines, 220 jobs, time 168 hours (1 week), several jobs connected, deadlines defined for all jobs except those connected, several machines (flashing red) excluded for certain interval of time. Cost and tardiness minimization

For more examples, continue. How to combine Job Shop Scheduling with Shift Work?