Solving The Job-Shop Scheduling Problem by Arena Simulation Software
Solving The Job-Shop Scheduling Problem by Arena Simulation Software
discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/236631006
CITATIONS READS
0 2,286
5 authors, including:
Wael Hassanein
King Abdulaziz University
5 PUBLICATIONS 6 CITATIONS
SEE PROFILE
All content following this page was uploaded by Wael Hassanein on 18 February 2017.
The user has requested enhancement of the downloaded file. All in-text references underlined in blue are added to the original document
and are linked to publications on ResearchGate, letting you access and read them immediately.
International Journal of Engineering Innovation & Research
Volume 2, Issue 2, ISSN: 2277 – 5668
Abstract – The job-Shop Scheduling problem (JSSP) theoretical research has been a complete waste of time
attracted a lot of researchers from various research because it has given insights into the scheduling problem.
disciplines, mainly Operations Research, Management In this research we want to reduce this gap, we also want
Science, Computer Science, and Manufacture Science for the to give the practitioners a friendly interface program
last 50 years. JSSP is a typical NP-hard problem in the
which they can deal with comfortably. Discrete event
strong sense. Although the literature is full of researches
concerning the JSSP, practitioners are not able to get benefit simulation is very promising in solving the real life JSSP.
of the majority of these researches because of the We chose Arena simulation software as it's a very
assumptions which take the problem very far away from the powerful tool plus it's very famous as simulation software
real life JSSP. The aim of our research is to build a and a lot of the practitioners are familiar with it. Also we
simulation model for the JSSP to be able to relax some of can get very beneficial statistical reports from Arena after
these assumptions to simulate the real life JSSP. We used each run containing some valuable information like;
discrete event simulation as it's suitable for the JSSP. We machine utilization, idle time for each machine, queue
used Arena simulation software version 14 to build the model length, waiting time, and other information.
on a Dell® Vostro PC (Intel® Core(TM) i5–2400 CPU @
3.10GHZ with 4 GB RAM).In this paper we will just show
the basic model which is able to solve the famous II. LITERATURE REVIEW
benchmarks for the JSSP to prove that our model is ready
for the real life JSSP. In the following papers we will show A very big number of different methods were used to
how to relax some of these assumptions one by one. The solve the JSSP. These methods are classified into different
computational results for 9 benchmarks of different sizes approaches, two of them are common in all the researches
showed that the proposed model is both effective and like for example these recent papers [5, 6, 7, and 8]. First
efficient. It gave good solutions in reasonable amounts of
approach is exact methods, such as branch and bound,
time.
linear programming and Lagrangian relaxation. These
Keywords — Job-Shop Scheduling Problem, Makespan, exact methods guarantee global convergence and have
Simulation, Arena. been successful in solving small instances. However, they
require a very high computing time as the size of problem
I. INTRODUCTION increases plus they are not capable of dealing with
stochastic problems. Second approach is Approximation
The job shop scheduling problem is a practical problem Methods, such as the shifting bottleneck approach, particle
and has numerous applications in manufacturing and swarm optimization, ant colony optimization, simulated
supply chain scheduling problems [1]. Job-Shop annealing, Tabu search, genetic algorithm, neural network,
scheduling refers to assigning jobs to machines satisfying immune algorithm, differential evolution and others. Some
the precedence and resource constraints over time such of the researchers added one or two additional approaches
that certain objective(s) is optimized, These objectives can for example in [9] the authors added dispatching rules and
be minimization of makespan, minimization of maximum simulation-based approach as a third one, in which we can
lateness, or minimization of the number of tardy jobs etc. build a simulation model based on dispatching rules and
The JSSP for the number of machines ≥ 2 is a typical NP- this is what we will do in this research. Additional two
hard problem in the strong sense[2], which means that the approaches were added by [10] which are, rule-based
number of possible schedules grows exponentially with approach, and simulation approach. Recently researchers
the number of orders. In history, the famous test problem are adopting hybrid techniques in which two or more
named FT10 which consists of 10 jobs and 10 machines, methods are combined in order to get the advantages of all
developed by Muth and Thompson [3] took more than 20 used methods as in [5, 11, 12, and 13]. The author in [5]
years until solved by Carlier and Pinson [4]. Because of collected 14 techniques which are called state-of-the-art
the JSSP complexity some researchers tried to solve the algorithms, these algorithms are a combination of recent
problem just to justify their models or heuristics and prove and older solution techniques, some of them constituting
that they are capable of handling such complex problems. the best approximation algorithms for the JSSP. These
After these decades and this huge number of researches, state-of-the-art algorithms are; SB [14], SBGA [15],
still there is a big gap between the analytical work and the TSAB [16], I-TSAB [17], GRASP [18], HGA [19],
real life problem. Pinedo [1] stated that advances in ACOFT [20], TSSA [21], BV [22], TSSB [23], DS [24],
scheduling theory have had only a limited impact on FL [25], SVS [26], and HA [27].
scheduling in practice, this doesn’t mean that the
Copyright © 2013 IJEIR, All right reserved
161
International Journal of Engineering Innovation & Research
Volume 2, Issue 2, ISSN: 2277 – 5668
III. PROBLEM DESCRIPTION Part one: will be responsible for creating jobs,
defining all variables and attributes, releasing jobs,
The definition and problem assumptions for the JSSP is and starting sequencing.
available in the literature in many references, here is the Part two: will be responsible for the machines, the
definition and problem assumption from two recent papers manufacturing process, and the exportation of the
[6, 7]. In the JSSP there are n jobs and m machines. Each information to the Excel file. This part will be done
job has a fixed processing route which traverses some or for each machine. The same process will be repeated
all the machines in a predetermined order. The for all machines.
manufacturing process to be performed on one machine is Part three: In this part jobs will exit the
called an operation of the job, and each operation should manufacturing system, and the system will dispose the
be processed on a particular machine. The objective is to parts.
schedule operations on machines so that the makespan Now we will discuss the three parts in details:
(maximum completion time) is minimized. Problem Part one will include the four modules shown in Fig. 1 as
assumptions can be stated as follows: follows:
1. Processing times are deterministic.
2. All jobs are ready to be processed at time zero.
3. Only one job can be processed on each machine at a
given period of time.
4. Each job visits each machine once at most.
5. The machines are continuously available. Fig.1. Part 1
6. There's only one machine of each type of machines.
7. No preemption of operations is allowed. - Create module from the Basic Process project bar,
8. The transportation times between different machines time between arrivals will be constant, value will be
are neglected. (0), entities per arrival will be (1), and maximum
9. The setup times for different jobs are neglected or arrivals will be (4).
added to the processing time. - Assign module also from the Basic Process project
The previous definition and assumptions are for the bar in which we will define all variables and attributes
classical JSSP which we will handle in this paper to show concerning: part index, entity type, entity sequence,
our basic model by Arena software. Even this classical and an attribute to generate random numbers which
JSSP with these assumptions is an NP-hard problem which we will call random.
researchers for the last 5 decades plus handled its - Station module from Advanced Transfer project bar
benchmarks to find optimum solutions for them or to which we will use to release jobs.
prove their different methods with this complex problem. - Route module from Advanced Transfer project bar
which we will use to start sequencing.
IV. PROPOSED MODEL Part two will include the four modules for each machine
shown in Fig. 2 as follows:
Now we will build our model using Arena software. The
model will export some information to Microsoft Excel
file as we will show. In the beginning we have to prepare
an Excel file, we have to define names for certain fields
which we will use to export the information, we will name
it results. After preparing the excel file we are ready to Fig.2. Part 2
build the model. We will use an example to show our
solution methodology, the example consists of 4 machines, - Station module from Advanced Transfer project bar
4 jobs as shown in table 1 it's required to give the best which we will use to receive jobs.
schedule with the minimum makespan. - Process module from the Basic Process project bar, it
Table 1: A 4x4 JSS example will represent the machine and simulating the
J Processing Sequence (Processing time) manufacturing process, in the field Action we will
select Seize Delay Release, for Resources we will add
1 2(2) 1(1) 4(2) 3(1)
a resource, name it (for example cell1), and put the
2 4(3) 2(1) 3(3) 1(2) quantity for it (here it's one), in the Delay Type we
3 1(1) 3(3) 4(2) 2(1) will choose Expression and it will be process time.
- ReadWrite module from Advanced Process project
4 3(2) 2(2) 1(2) 4(3) bar which we will use to export some information to
the Excel file. In type we will select Write to file, in
The model will be divided into three parts: Arena file name we will select the predefined Excel
file, in the Recordset ID we will select the predefined
name for the three fields in the Excel sheet, and in
assignments we will add the Entity.Type as an
Copyright © 2013 IJEIR, All right reserved
162
International Journal of Engineering Innovation & Research
Volume 2, Issue 2, ISSN: 2277 – 5668
attribute, the Process Time as an attribute, and operation start time, and finally column 4 represents the
Entity.StartTime as Other. operation finish time. We can check the operations times
- Route module from Advanced Transfer project bar and the feasibility of the solution, if it’s ok so our model is
which we will use to release the jobs by sequence. In verified. We can also generate the Ganttchart as in Fig. 4.
Destination Type we will choose By Sequence. Because our example here is small we can make the FIFO
Part three will include the two modules shown in fig 3 as schedule manually and compare it to the generated one
follows: from the model, and this will be the validation for the
model. Now we will use the model to solve 9 famous
benchmarks with different sizes from the literature to
make sure that our model is representing the JSSP and it's
capable of handling such problems.
Table 2: Schedule for machine 1 for the FIFO scheduling
rule
Fig.3. Part 3
Machine1
- Station module from Advanced Transfer project bar Job No. Processing time Start time Finish time
which we will use for the jobs to exit the
3 1 0 1
manufacturing system.
- Dispose module from the Basic Process project bar 1 1 2 3
which means that the system will dispose the jobs. 4 2 4 6
Still two things we have to do in the Arena model to be 2 2 8 10
ready to run it:
1. From the Advanced Process project bar we will select
Statistic, in the Name we will write makespan, in type
we will select output, in Expression we will build an
expression to get the makespan which is the
completion time of all jobs, and finally in output file
we will name a file makespan.dat and put it in the
same folder with the model. This file (makespan.dat)
will record the makespan for each replication, we will
open this file later with the Output Analyzer.
2. From the Advanced Process project bar we will select Fig.4. Ganttchart for the FIFO scheduling rule
File, in the Name we will write results in Access type
we will select Microsoft Excel, in Operating System
File Name we will select the predefined Excel File, VI. RESULTS AND DISCUSSION
and finally in Recordsets we will add the named
ranges from the Excel file. This is the file which will Now we will show how to run the model for any
receive the exported data from the ReadWrite module. number of replications then get the minimum makespan
and the related schedule. From Run menu we will select
setup then Replication Parameters and put for example
V. VERIFICATION AND VALIDATION 100 in the Number of Replications. We have to change the
dispatching rule for all queues to Highest Attribute Value,
Model verification and validation are critical in the from the Basic Process project bar we will select Queue,
development of a simulation model [28]. Verification go to Type, and select Highest Attribute Value, then in the
ensures that the model is conducted correctly, while Attribute Name we will select Random the attribute we
validation ensures that the model represents the real prepared before in the Assign module to generate random
system and that the model is truly representative of that numbers. Now we are ready again to run the model, this
system. Sargent [28] mentioned different approaches to time for 100 replications and random queue discipline.
verify and validate any simulation model, then in his After running the model we will get a file with the name
research summary he said ". Unfortunately, there is no set of results.dat, we will open this file with the output
of specific tests that can easily be applied to determine the analyzer and generate a DIF file with the same name. This
correctness of a model. Furthermore, no algorithm exists DIF file is readable by Microsoft Excel, we will find 2
to determine what techniques or procedures to use. Every rows the first one will contain the replication number
simulation project presents a new and unique challenge to while the second one will contain the Makespan. From
the model development team". To verify our model here Excel we can get the minimum makespan with the
we should just review the data entered to the model. We corresponding replication number(s), it's expected to have
will run the model with FIFO as a scheduling rule and go more than one solution with the same makespan and any
to the Excel file to check the resulting schedule for each one of them is accepted.
machine. Table 2 shows the schedule for machine one as After getting the minimum makespan and the number of
an example, column 1 represents the job sequence, column corresponding replication we will go to the Excel file
2 represents the operation time, column 3 represents the
Copyright © 2013 IJEIR, All right reserved
163
International Journal of Engineering Innovation & Research
Volume 2, Issue 2, ISSN: 2277 – 5668
(results), go to the required replication and we should find will use the same formula as in [5] to calculate the
all required scheduling information for each machine Makespan Relative Error (MRE) of the best makespan
containing; the processing sequence, the processing time found by our model. Makespan Relative Error of the best
for each operation, start and finish times for each makespan fbest found, with respect to a reference makespan
operation. We can also generate Ganttchart from these which is typically a lower bound LB. The relative error is
information. expressed as a ratio (MRE = 0 indicates that the
There's no guarantee that this is the optimum solution, corresponding instance is solved optimally) and is
and of course we can raise the number of replications as computed according to the following formula, MRE = 100
we want, the only constraint is the time consumed to get × [(fbest – LB)/LB]. This formula is originally from [36],
the solution for the model and it depends on the computer For example, for the first problem FT06 the optimum
power. solution is 55 and the best makespan we got is 58 so the
As we said we will test our model with several MRE = 100 x [(58-55)/55] = 5.45.
benchmark instances with different sizes, these We recorded two times to the nearest minute, first one is
benchmarks and many others could be found in the OR the time for simulating all replications and the second one
library [29] and other references like [30, 31, 32, 33, 34, is the time to generate the reports with the required
and 35]. Table 3 shows different values for best makespan statistical analysis. We will not use the reports in the basic
for different number of replications with their model as we exported all needed information to the DAT
corresponding computation times. We will run the model file, and the Excel file.
with the FIFO scheduling rule then with the random
scheduling rule for 100, 1000, and 2000 replications. We
AUTHOR’S PROFILE