Abstract: This paper proposes a self-organization-based approach for real-time systems design. The addressed issue is the mapping of an application onto an architecture of heterogeneous processors while optimizing both makespan and reliability. Since this problem is NP-hard, a heuristic algorithm is used to obtain efficiently approximate solutions. The proposed approach takes into consideration the quality as well as the diversity of solutions. Indeed, an alternate treatment of the two objectives allows to produce solutions of good quality while a self-organization approach based on the neighborhood structure is used to reorganize solutions and consequently to enhance their diversity. Produced solutions make different compromises between the makespan and the reliability giving the user the possibility to select the solution suited to his (her) needs.
Abstract: In this paper, a mixed integer linear programming (MILP) model is presented to solve the flexible job shop scheduling problem (FJSP). This problem is one of the hardest combinatorial problems. The objective considered is the minimization of the makespan. The computational results of the proposed MILP model were compared with those of the best known mathematical model in the literature in terms of the computational time. The results show that our model has better performance with respect to all the considered performance measures including relative percentage deviation (RPD) value, number of constraints, and total number of variables. By this improved mathematical model, larger FJS problems can be optimally solved in reasonable time, and therefore, the model would be a better tool for the performance evaluation of the approximation algorithms developed for the problem.
Abstract: The job-shop scheduling problem (JSSP) is an important decision facing those involved in the fields of industry, economics and management. This problem is a class of combinational optimization problem known as the NP-hard problem. JSSPs deal with a set of machines and a set of jobs with various predetermined routes through the machines, where the objective is to assemble a schedule of jobs that minimizes certain criteria such as makespan, maximum lateness, and total weighted tardiness. Over the past several decades, interest in meta-heuristic approaches to address JSSPs has increased due to the ability of these approaches to generate solutions which are better than those generated from heuristics alone. This article provides the classification, constraints and objective functions imposed on JSSPs that are available in the literature.
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: Multiprocessor task scheduling problem for dependent
and independent tasks is computationally complex problem. Many
methods are proposed to achieve optimal running time. As the
multiprocessor task scheduling is NP hard in nature, therefore, many
heuristics are proposed which have improved the makespan of the
problem. But due to problem specific nature, the heuristic method
which provide best results for one problem, might not provide good
results for another problem. So, Simulated Annealing which is meta
heuristic approach is considered. It can be applied on all types of
problems. However, due to many runs, meta heuristic approach takes
large computation time. Hence, the hybrid approach is proposed by
combining the Duplication Scheduling Heuristic and Simulated
Annealing (SA) and the makespan results of Simple Simulated
Annealing and Hybrid approach are analyzed.
Abstract: In this paper, we propose two algorithms to optimally
solve makespan and total completion time scheduling problems with
learning effect and job dependent delivery times in a single machine
environment. The delivery time is the extra time to eliminate adverse
effect between the main processing and delivery to the customer. In
this paper, we introduce the job dependent delivery times for some
single machine scheduling problems with position dependent learning
effect, which are makespan are total completion. The results with
respect to two algorithms proposed for solving of the each problem
are compared with LINGO solutions for 50-jobs, 100-jobs and 150-
jobs problems. The proposed algorithms can find the same results in
shorter time.
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: Batch production plants provide a wide range of
scheduling problems. In pharmaceutical industries a batch process
is usually described by a recipe, consisting of an ordering of tasks
to produce the desired product. In this research work we focused
on pharmaceutical production processes requiring the culture of
a microorganism population (i.e. bacteria, yeasts or antibiotics).
Several sources of uncertainty may influence the yield of the culture
processes, including (i) low performance and quality of the cultured
microorganism population or (ii) microbial contamination. For
these reasons, robustness is a valuable property for the considered
application context. In particular, a robust schedule will not collapse
immediately when a cell of microorganisms has to be thrown away
due to a microbial contamination. Indeed, a robust schedule should
change locally in small proportions and the overall performance
measure (i.e. makespan, lateness) should change a little if at all.
In this research work we formulated a constraint programming
optimization (COP) model for the robust planning of antibiotics
production. We developed a discrete-time model with a multi-criteria
objective, ordering the different criteria and performing a
lexicographic optimization. A feasible solution of the proposed
COP model is a schedule of a given set of tasks onto available
resources. The schedule has to satisfy tasks precedence constraints,
resource capacity constraints and time constraints. In particular
time constraints model tasks duedates and resource availability
time windows constraints. To improve the schedule robustness, we
modeled the concept of (a, b) super-solutions, where (a, b) are input
parameters of the COP model. An (a, b) super-solution is one in
which if a variables (i.e. the completion times of a culture tasks)
lose their values (i.e. cultures are contaminated), the solution can be
repaired by assigning these variables values with a new values (i.e.
the completion times of a backup culture tasks) and at most b other
variables (i.e. delaying the completion of at most b other tasks).
The efficiency and applicability of the proposed model is
demonstrated by solving instances taken from a real-life
pharmaceutical company. Computational results showed that
the determined super-solutions are near-optimal.
Abstract: Workflow scheduling is an important part of cloud
computing and based on different criteria it decides cost, execution
time, and performances. A cloud workflow system is a platform
service facilitating automation of distributed applications based on
new cloud infrastructure. An aspect which differentiates cloud
workflow system from others is market-oriented business model, an
innovation which challenges conventional workflow scheduling
strategies. Time and Cost optimization algorithm for scheduling
Hybrid Clouds (TCHC) algorithm decides which resource should be
chartered from public providers is combined with a new De-De
algorithm considering that every instance of single and multiple
workflows work without deadlocks. To offset this, two new concepts
- De-De Dodging Algorithm and Priority Based Decisive Algorithm -
combine with conventional deadlock avoidance issues by proposing
one algorithm that maximizes active (not just allocated) resource use
and reduces Makespan.
Abstract: Grid is an environment with millions of resources
which are dynamic and heterogeneous in nature. A computational
grid is one in which the resources are computing nodes and is meant
for applications that involves larger computations. A scheduling
algorithm is said to be efficient if and only if it performs better
resource allocation even in case of resource failure. Resource
allocation is a tedious issue since it has to consider several
requirements such as system load, processing cost and time, user’s
deadline and resource failure. This work attempts in designing a
resource allocation algorithm which is cost-effective and also targets
at load balancing, fault tolerance and user satisfaction by considering
the above requirements. The proposed Budget Constrained Load
Balancing Fault Tolerant algorithm with user satisfaction (BLBFT)
reduces the schedule makespan, schedule cost and task failure rate
and improves resource utilization. Evaluation of the proposed
BLBFT algorithm is done using Gridsim toolkit and the results are
compared with the algorithms which separately concentrates on all
these factors. The comparison results ensure that the proposed
algorithm works better than its counterparts.
Abstract: This paper presents optimization of makespan for ‘n’
jobs and ‘m’ machines flexible job shop scheduling problem with
sequence dependent setup time using genetic algorithm (GA)
approach. A restart scheme has also been applied to prevent the
premature convergence. Two case studies are taken into
consideration. Results are obtained by considering crossover
probability (pc = 0.85) and mutation probability (pm = 0.15). Five
simulation runs for each case study are taken and minimum value
among them is taken as optimal makespan. Results indicate that
optimal makespan can be achieved with more than one sequence of
jobs in a production order.
Abstract: This research proposes a preemptive fuzzy goal programming model for multi-objective multi-mode resource constrained project scheduling problem. The objectives of the problem are minimization of the total time and the total cost of the project. Objective in a multi-mode resource-constrained project scheduling problem is often a minimization of makespan. However, both time and cost should be considered at the same time with different level of important priorities. Moreover, all elements of cost functions in a project are not included in the conventional cost objective function. Incomplete total project cost causes an error in finding the project scheduling time. In this research, preemptive fuzzy goal programming is presented to solve the multi-objective multi-mode resource constrained project scheduling problem. It can find the compromise solution of the problem. Moreover, it is also flexible in adjusting to find a variety of alternative solutions.
Abstract: We model the process of a data center as a multi- objective problem of mapping independent tasks onto a set of data center machines that simultaneously minimizes the energy consump¬tion and response time (makespan) subject to the constraints of deadlines and architectural requirements. A simple technique based on multi-objective goal programming is proposed that guarantees Pareto optimal solution with excellence in convergence process. The proposed technique also is compared with other traditional approach. The simulation results show that the proposed technique achieves superior performance compared to the min-min heuristics, and com¬petitive performance relative to the optimal solution implemented in UNDO for small-scale problems.
Abstract: In the paper we discuss the influence of the route
flexibility degree, the open rate of operations and the production type
coefficient on makespan. The flexible job-open shop scheduling
problem FJOSP (an extension of the classical job shop scheduling) is
analyzed. For the analysis of the production process we used a
hybrid heuristic of the GRASP (greedy randomized adaptive search
procedure) with simulated annealing algorithm. Experiments with
different levels of factors have been considered and compared. The
GRASP+SA algorithm has been tested and illustrated with results for
the serial route and the parallel one.
Abstract: We introduce an extended resource leveling model that abstracts real life projects that consider specific work ranges for each resource. Contrary to traditional resource leveling problems this model considers scarce resources and multiple objectives: the minimization of the project makespan and the leveling of each resource usage over time. We formulate this model as a multiobjective optimization problem and we propose a multiobjective genetic algorithm-based solver to optimize it. This solver consists in a two-stage process: a main stage where we obtain non-dominated solutions for all the objectives, and a postprocessing stage where we seek to specifically improve the resource leveling of these solutions. We propose an intelligent encoding for the solver that allows including domain specific knowledge in the solving mechanism. The chosen encoding proves to be effective to solve leveling problems with scarce resources and multiple objectives. The outcome of the proposed solvers represent optimized trade-offs (alternatives) that can be later evaluated by a decision maker, this multi-solution approach represents an advantage over the traditional single solution approach. We compare the proposed solver with state-of-art resource leveling methods and we report competitive and performing results.
Abstract: In this paper we address a multi-objective scheduling problem for unrelated parallel machines. In unrelated parallel systems, the processing cost/time of a given job on different machines may vary. The objective of scheduling is to simultaneously determine the job-machine assignment and job sequencing on each machine. In such a way the total cost of the schedule is minimized. The cost function consists of three components, namely; machining cost, earliness/tardiness penalties and makespan related cost. Such scheduling problem is combinatorial in nature. Therefore, a Simulated Annealing approach is employed to provide good solutions within reasonable computational times. Computational results show that the proposed approach can efficiently solve such complicated problems.
Abstract: The job shop scheduling problem (JSSP) is a
notoriously difficult problem in combinatorial optimization. This
paper presents a hybrid artificial immune system for the JSSP with the
objective of minimizing makespan. The proposed approach combines
the artificial immune system, which has a powerful global exploration
capability, with the local search method, which can exploit the optimal
antibody. The antibody coding scheme is based on the operation based
representation. The decoding procedure limits the search space to the
set of full active schedules. In each generation, a local search heuristic
based on the neighborhood structure proposed by Nowicki and
Smutnicki is applied to improve the solutions. The approach is tested
on 43 benchmark problems taken from the literature and compared
with other approaches. The computation results validate the
effectiveness of the proposed algorithm.
Abstract: During last decades, developing multi-objective
evolutionary algorithms for optimization problems has found
considerable attention. Flexible job shop scheduling problem, as an
important scheduling optimization problem, has found this attention
too. However, most of the multi-objective algorithms that are
developed for this problem use nonprofessional approaches. In
another words, most of them combine their objectives and then solve
multi-objective problem through single objective approaches. Of
course, except some scarce researches that uses Pareto-based
algorithms. Therefore, in this paper, a new Pareto-based algorithm
called controlled elitism non-dominated sorting genetic algorithm
(CENSGA) is proposed for the multi-objective FJSP (MOFJSP). Our
considered objectives are makespan, critical machine work load, and
total work load of machines. The proposed algorithm is also
compared with one the best Pareto-based algorithms of the literature
on some multi-objective criteria, statistically.
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 the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. Minimizing the makespan and maximization the net present value (NPV) are the two common objectives that have been investigated in the literature. We apply one evolutionary algorithm named multiobjective particle swarm optimization (MOPSO) to find Pareto front solutions. We used standard sets of instances from the project scheduling problem library (PSPLIB). The results are computationally compared respect to different metrics taken from the literature on evolutionary multi-objective optimization.