Birger Raa
This case study handles the job shop scheduling problem in a flow shop at the case company. A simulation model was built to compare several algorithms based on priority rules. The effect of manpower allocation on the problem was included. An implementation plan is proposed for the suggested algorithm. Data obtained from a condensed implementation validated the theoretical results.
Order sequencing, sequence dependent, simulation, priority rules.
Electronic And Other Electrical Equipment And Components, Except Computer Equipment
> 5.000
0% - 5%
Products tailored to customer specifications
Make-to-order (one-of-a-kind)
Shop fabrication
Project Manager
Production planning
Partly True
Reduction in lead time

Scheduling at the company is dynamic, it happens on a rolling horizon as opposed to the typical situations in this subject. There is no distinctive start or end point from the schedule as jobs are continuously added to the system. As a consequence, jobs with an availability time larger than the current time are unknown. The schedule has to be reevaluated continuously as new jobs are added to the system. The makespan of the schedule cannot be defined because of this endless character. The performance of a schedule will be evaluated by looking at the leadtime of production orders, which is defined as its completion time minus its availability time.

Another difference in comparison to the general job shop problem is the presence of sequence dependent setup times. That means that the total production times are not known exactly until the schedule is made. A production order at the shop can only be started when the Processor is available, and an Operator is ready to start the production.

Order sequencing is the search for a schedule that defines start times of production orders in such a way that certain objective functions are optimized. The objective in the Piping production environment at the case company was to minimise average lead times of the products. Production lines at the company have a higher variety and lower volume than typical mass production lines. Piping section has 20 workstations, most of them contain one or two identical CNC-machines. Operators perform a fixed setup at the start of every production order and a variable changeover depending on the current settings of the machine and the required settings of the next production order. The used dataset contains 660 different order types, on average these are produced on only 2 workstations.

The Piping facility is a flow shop; the flow of production orders between workstations is always in the same direction. Further important characteristics are the rolling horizon and the sequence dependent changeover times. New production orders are continuously added to the system, there is no clearly defined start or end point. The situation is called dynamic. Further, the changeover time of a workstation is both dependent on the last produced product type and the next one. The objective is to find an algorithm that will provide the operators what production order they need to start next, in a way that minimizes overall lead times for the production facility.

A lot of variations exist on the traditional order sequencing problem and a lot of research has been done about it. A simulation model was built to evaluate several priority rules. The current sequencing method was implemented to validate the simulation and to have a reference point to evaluate possible improvements. Currently the operators combine a First-In-First-Out policy with a minimisation of changeovers. In general, they select the oldest production orders and within this group they will minimize the total amount of changeovers. The data obtained from the simulation was then compared to data from the production facility to validate the model. The simulation model approximated the real situation, though not with great precision. The simulation was also validated with a second dataset to confirm its robustness. The model allows rapid comparison of several priority rules. The simulation also provided means to optimize small adjustments to the sequencing algorithm. The model was made as general as possible to allow the company to evaluate the effect of several possible changes to the production environment, and to possibly be used for further research to optimise the production facility.


Several rules were tested in the company and the best performing rule was selected. The selected rule assigns to each production order the value of its changeover time (CO) plus its average processing time per operation (AVPRO). The next production order to be processed on a workstation, is then the production order with the lowest value from all available production orders. In the simulation, this rule decreased the average production leadtime per order type with more than 20%.

The implementation was started on one workstation. The initial results were promising; the obtained leadtime reduction of 25% was even larger than expected from simulation, while the leadtime of a control group lightly increased. It was expected that the leadtime of order types with a large value for AVPRO would increase, and this behaviour was observed from the implementation.