Abstract: This paper presents a genetic algorithm based permutation and non-permutation scheduling heuristics (GAPNP) to solve a multi-stage finite capacity material requirement planning (FCMRP) problem in automotive assembly flow shop with unrelated parallel machines. In the algorithm, the sequences of orders are iteratively improved by the GA characteristics, whereas the required operations are scheduled based on the presented permutation and non-permutation heuristics. Finally, a linear programming is applied to minimize the total cost. The presented GAPNP algorithm is evaluated by using real datasets from automotive companies. The required parameters for GAPNP are intently tuned to obtain a common parameter setting for all case studies. The results show that GAPNP significantly outperforms the benchmark algorithm about 30% on average.
Abstract: This paper aims to present non-population search algorithms called tabu search (TS), simulated annealing (SA) and variable neighborhood search (VNS) to minimize the total cost of capacitated MRP problem in multi-stage assembly flow shop with two alternative machines. There are three main steps for the algorithm. Firstly, an initial sequence of orders is constructed by a simple due date-based dispatching rule. Secondly, the sequence of orders is repeatedly improved to reduce the total cost by applying TS, SA and VNS separately. Finally, the total cost is further reduced by optimizing the start time of each operation using the linear programming (LP) model. Parameters of the algorithm are tuned by using real data from automotive companies. The result shows that VNS significantly outperforms TS, SA and the existing algorithm.
Abstract: The Flow Shop Scheduling Problem (FSSP) is a typical problem that is faced by production planning managers in Flexible Manufacturing Systems (FMS). This problem consists in finding the optimal scheduling to carry out a set of jobs, which are processed in a set of machines or shared resources. Moreover, all the jobs are processed in the same machine sequence. As in all the scheduling problems, the makespan can be obtained by drawing the Gantt chart according to the operations order, among other alternatives. On this way, an FMS presenting the FSSP can be modeled by Petri nets (PNs), which are a powerful tool that has been used to model and analyze discrete event systems. Then, the makespan can be obtained by simulating the PN through the token game animation and incidence matrix. In this work, we present an adaptive PN to obtain the makespan of FSSP by applying PN analytical tools.
Abstract: This paper studied the flow shop scheduling problem under machine availability constraints. The machines are subject to flexible preventive maintenance activities. The nonresumable scenario for the jobs was considered. That is, when a job is interrupted by an unavailability period of a machine it should be restarted from the beginning. The objective is to minimize the total tardiness time for the jobs and the advance/tardiness for the maintenance activities. To solve the problem, a genetic algorithm was developed and successfully tested and validated on many problem instances. The computational results showed that the new genetic algorithm outperforms another earlier proposed algorithm.
Abstract: This paper addresses minimizing the makespan of the
distributed permutation flow shop scheduling problem. In this
problem, there are several parallel identical factories or flowshops
each with series of similar machines. Each job should be allocated to
one of the factories and all of the operations of the jobs should be
performed in the allocated factory. This problem has recently gained
attention and due to NP-Hard nature of the problem, metaheuristic
algorithms have been proposed to tackle it. Majority of the proposed
algorithms require large computational time which is the main
drawback. In this study, a general variable neighborhood search
algorithm (GVNS) is proposed where several time-saving schemes
have been incorporated into it. Also, the GVNS uses the sophisticated
method to change the shaking procedure or perturbation depending
on the progress of the incumbent solution to prevent stagnation of the
search. The performance of the proposed algorithm is compared to
the state-of-the-art algorithms based on standard benchmark
instances.
Abstract: In this paper, mathematical models for permutation flow shop scheduling and job shop scheduling problems are proposed. The first problem is based on a mixed integer programming model. As the problem is NP-complete, this model can only be used for smaller instances where an optimal solution can be computed. For large instances, another model is proposed which is suitable for solving the problem by stochastic heuristic methods. For the job shop scheduling problem, a mathematical model and its main representation schemes are presented.
Abstract: This paper considers a scheduling problem in flexible
flow shops environment with the aim of minimizing two important
criteria including makespan and cumulative tardiness of jobs. Since
the proposed problem is known as an Np-hard problem in literature,
we have to develop a meta-heuristic to solve it. We considered
general structure of Genetic Algorithm (GA) and developed a new
version of that based on Data Envelopment Analysis (DEA). Two
objective functions assumed as two different inputs for each Decision
Making Unit (DMU). In this paper we focused on efficiency score of
DMUs and efficient frontier concept in DEA technique. After
introducing the method we defined two different scenarios with
considering two types of mutation operator. Also we provided an
experimental design with some computational results to show the
performance of algorithm. The results show that the algorithm
implements in a reasonable time.
Abstract: In this paper an ant colony optimization algorithm is
developed to solve the permutation flow shop scheduling problem. In
the permutation flow shop scheduling problem which has been vastly
studied in the literature, there are a set of m machines and a set of n
jobs. All the jobs are processed on all the machines and the sequence
of jobs being processed is the same on all the machines. Here this
problem is optimized considering two criteria, makespan and total
flow time. Then the results are compared with the ones obtained by
previously developed algorithms. Finally it is visible that our
proposed approach performs best among all other algorithms in the
literature.
Abstract: Re-entrant scheduling is an important search problem
with many constraints in the flow shop. In the literature, a number of
approaches have been investigated from exact methods to
meta-heuristics. This paper presents a genetic algorithm that encodes
the problem as multi-level chromosomes to reflect the dependent
relationship of the re-entrant possibility and resource consumption.
The novel encoding way conserves the intact information of the data
and fastens the convergence to the near optimal solutions. To test the
effectiveness of the method, it has been applied to the
resource-constrained re-entrant flow shop scheduling problem.
Computational results show that the proposed GA performs better than
the simulated annealing algorithm in the measure of the makespan
Abstract: The process of wafer fabrication is arguably the most
technologically complex and capital intensive stage in semiconductor
manufacturing. This large-scale discrete-event process is highly reentrant,
and involves hundreds of machines, restrictions, and
processing steps. Therefore, production control of wafer fabrication
facilities (fab), specifically scheduling, is one of the most challenging
problems that this industry faces. Dispatching rules have been
extensively applied to the scheduling problems in semiconductor
manufacturing. Moreover, lot release policies are commonly used in
this manufacturing setting to further improve the performance of such
systems and reduce its inherent variability. In this work, simulation is
used in the scheduling of re-entrant flow shop manufacturing systems
with an application in semiconductor wafer fabrication; where, a
simulation model has been developed for the Intel Five-Machine Six
Step Mini-Fab using the ExtendTM simulation environment. The
Mini-Fab has been selected as it captures the challenges involved in
scheduling the highly re-entrant semiconductor manufacturing lines.
A number of scenarios have been developed and have been used to
evaluate the effect of different dispatching rules and lot release
policies on the selected performance measures. Results of simulation
showed that the performance of the Mini-Fab can be drastically
improved using a combination of dispatching rules and lot release
policy.
Abstract: We consider a typical problem in the assembly of
printed circuit boards (PCBs) in a two-machine flow shop system to
simultaneously minimize the weighted sum of weighted tardiness and
weighted flow time. The investigated problem is a group scheduling
problem in which PCBs are assembled in groups and the interest is to
find the best sequence of groups as well as the boards within each
group to minimize the objective function value. The type of setup
operation between any two board groups is characterized as carryover
sequence-dependent setup time, which exactly matches with the real
application of this problem. As a technical constraint, all of the
boards must be kitted before the assembly operation starts (kitting
operation) and by kitting staff. The main idea developed in this paper
is to completely eliminate the role of kitting staff by assigning the
task of kitting to the machine operator during the time he is idle
which is referred to as integration of internal (machine) and external
(kitting) setup times. Performing the kitting operation, which is a
preparation process of the next set of boards while the other boards
are currently being assembled, results in the boards to continuously
enter the system or have dynamic arrival times. Consequently, a
dynamic PCB assembly system is introduced for the first time in the
assembly of PCBs, which also has characteristics similar to that of
just-in-time manufacturing. The problem investigated is
computationally very complex, meaning that finding the optimal
solutions especially when the problem size gets larger is impossible.
Thus, a heuristic based on Genetic Algorithm (GA) is employed. An
example problem on the application of the GA developed is
demonstrated and also numerical results of applying the GA on
solving several instances are provided.
Abstract: This paper aims to develop an algorithm of finite
capacity material requirement planning (FCMRP) system for a multistage
assembly flow shop. The developed FCMRP system has two
main stages. The first stage is to allocate operations to the first and
second priority work centers and also determine the sequence of the
operations on each work center. The second stage is to determine the
optimal start time of each operation by using a linear programming
model. Real data from a factory is used to analyze and evaluate the
effectiveness of the proposed FCMRP system and also to guarantee a
practical solution to the user. There are five performance measures,
namely, the total tardiness, the number of tardy orders, the total
earliness, the number of early orders, and the average flow-time. The
proposed FCMRP system offers an adjustable solution which is a
compromised solution among the conflicting performance measures.
The user can adjust the weight of each performance measure to
obtain the desired performance. The result shows that the combination
of FCMRP NP3 and EDD outperforms other combinations
in term of overall performance index. The calculation time for the
proposed FCMRP system is about 10 minutes which is practical for
the planners of the factory.
Abstract: One of the criteria in production scheduling is Make
Span, minimizing this criteria causes more efficiently use of the
resources specially machinery and manpower. By assigning some
budget to some of the operations the operation time of these activities
reduces and affects the total completion time of all the operations
(Make Span). In this paper this issue is practiced in parallel flow
shops. At first we convert parallel flow shop to a network model and
by using a linear programming approach it is identified in order to
minimize make span (the completion time of the network) which
activities (operations) are better to absorb the predetermined and
limited budget. Minimizing the total completion time of all the
activities in the network is equivalent to minimizing make span in
production scheduling.
Abstract: There are many real world problems in which
parameters like the arrival time of new jobs, failure of resources, and
completion time of jobs change continuously. This paper tackles the
problem of scheduling jobs with random due dates on multiple
identical machines in a stochastic environment. First to assign jobs to
different machine centers LPT scheduling methods have been used,
after that the particular sequence of jobs to be processed on the
machine have been found using simple stochastic techniques. The
performance parameter under consideration has been the maximum
lateness concerning the stochastic due dates which are independent
and exponentially distributed. At the end a relevant problem has been
solved using the techniques in the paper..
Abstract: This study compares three meta heuristics to minimize makespan (Cmax) for Hybrid Flow Shop (HFS) Scheduling Problem with Parallel Machines. This problem is known to be NP-Hard. This study proposes three algorithms among improvement heuristic searches which are: Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS). SA and TS are known as deterministic improvement heuristic search. GA is known as stochastic improvement heuristic search. A comprehensive comparison from these three improvement heuristic searches is presented. The results for the experiments conducted show that TS is effective and efficient to solve HFS scheduling problems.