Hybrid approach using simulation-based optimisation for job shop scheduling problems

Abstract

In this paper, we present a hybrid modelling approach and formulation using simulation-based optimisation (SbO) for solving complex problems, viz., job shop scheduling. The classical job shop scheduling problem is NP-Hard. Traditionally, the problem is modelled as a Mixed-Integer Programming (MIP) model and solved using exact algorithms (branch-and-bound, branch-and-cut, etc) or using meta-heuristics (Genetic Algorithm, Particle Swarm Optimisation, etc). In our hybrid SbO approach, we propose a modified formulation of the scheduling problem where the operational aspects of the job shop are captured only in the simulation model. Two new decision variables, controller delays and queue priorities, are introduced. The performances of the MIP-based approach and the proposed hybrid approach are compared through the number of decision variables, run time and the objective values for select deterministic benchmark problem instances. The results clearly indicate that the hybrid approach outperforms the traditional MIP for all large-scale problems, resulting in solutions closer to optimum in a much lesser computational time. Interestingly, it is also observed that the introduction of an ‘error’ term in the objective of the deterministic problem improves performance. Finally, the performance of the proposed SbO approach is analysed for stochastic job shops.

Appendix

Each instance in the benchmark library consists of a line of description followed by a line containing the number of jobs and the number of machines. Next is one line for each job, listing the machine number and processing time for each step of the job. The machines are numbered starting with 0. Table A1 shows the ft10 instance.

Klemmt et al (2009) have modified the data set in Table A1 to use an 8 × 10 job shop. This data set is called ft08 and is obtained by removing the last two rows from the Table A1. From Table A1, sorting out the data into processing time and sequence.

The functions written in the model are:

• InitializeJob(): All entities are initialised by assigning their respective sequences and the priority for the first machine that is visited in their sequence.

• AssignControllerDelay(): When implementing delay schedules, this function is used to delay a job before it proceeds to the next machine in its sequence. For non-delay schedules, the function returns a value 0.

• routing(): This function is used to implement the sequence for each job. Each time a job leaves a machine, this function is called to route it to the next machine in its sequence.

• AssignInterDelay(): This function is used to assign the queue priorities of each job on each machine. This function is recalled each time after a new routing occurs.

• ControllerDelayTimes(): This function calculates the time spent by an entity before entering the queue of the next machine in its sequence.

• DelayTimes(): This function calculates the time spent by the job in the queue of a machine.

• BeforeProcessing(): This function is called just before a job seizes a machine resource. It notes the actual start time of servicing by calling function ActualStartTimes() and also calls DelayTimes().

• AfterProcessing(): This function is called after a job releases the machine resource. It notes the time at which the machine was released by calling the function EndTimes(). It also calls JobSequence() to read the next machine number and AssignInterDelay().

• AssignProcessTime(): This function is called once the job enters the delay of the machine. The processing time corresponding to the job and the machine is accessed from the ‘processingtimes’ table, which holds all the processing times.

Table A1

Table A1 Fisher and Thompson 10 × 10 instance, alternate name (mt10)

Table A2

Table A2 Processing times for Fisher and Thompson 8 × 10 instance

Table A3

Table A3 Sequences for Fisher and Thompson 8 × 10 instance