Jose Maria A. et al. have presented an overview of the multi objective shortest path problem and a review of essential and recent issues regarding the methods to its solution. They further explored a multi objective evolutionary algorithm as applied to the MSPP and describe its behavior in terms of diversity of computational complexity, optimality and solutions. Results showed that the evolutionary algorithm could find diverse solutions to the MSPP in polynomial time (based on several network instances) and could be an alternative when other methods were trapped by the tractability problem. It also showed that the MOEA was a good alternative in finding a subset of efficient solutions to the MSPP. It was particularly beneficial when intractability and memory issues had become obstructions to find efficient solutions to the MSPP-related problems.
Rahim A et al. [59] have addressed the problem of time-dependent shortest multimodal path in complex and large urban areas. This problem was one of the important and practical problems in several fields such as transportation, and recently invites the research focus due to developments in new application areas. An acquainted evolutionary algorithm, in which chromosomes with variable lengths and particularly defined evolutionary stages were used, to solve the problem. The proposed solution was tested across the dataset of city of Tehran. The evaluation consists of computing multimodal shortest path between 250 randomly selected pairs of origins and destination points with various distances. It was assumed that three modes of walking, bus, and subway were used to travel between points. Moreover, some tests were performed over the dataset to illustrate the strength of method. The experimental results and related indices such as convergence plot showed that the proposed algorithm could find optimum path according to applied constraints.
C. Chitra and P. Subbaraj [60] have presented Multi objective Optimization Solution for Shortest Path Routing Problem. The shortest routing path problem was a multi objective non linear optimization problem with constraints. This problem had been addressed by considering Quality of service parameters, delay and cost objectives separately or as a weighted sum of both objectives. Multi objective evolutionary algorithms can find multiple Pareto optimal solutions in one single run and this ability makes them attractive for solving problems with multiple and conflicting objectives. They used an elitist multi objective evolutionary algorithm based on the Non-dominated Sorting Genetic Algorithm (NSGA), for solving the dynamic shortest path routing problem in computer networks. A priority-based encoding scheme was proposed for population initialization. Elitism ensured that the best solution did not deteriorate in the next generations. Results for a sample test network had been presented to demonstrate the capabilities of the proposed approach to generate well-distributed Pareto optimal solutions of dynamic routing problem in one single run. The results obtained by NSGA were compared with single objective weighting factor method for which Genetic Algorithm (GA) was applied.
Subbaraj Potti and Chitra Chinnasamy [70] have propose a new multi-objective approach, Strength Pareto Evolutionary Algorithm (SPEA), to solve the shortest routing path problem. The routing problem was explicated as a multi-objective mathematical programming problem which attempted to minimize both cost and delay objectives simultaneously. SPEA handled the shortest path routing problem as a true multi-objective optimization problem with competing and non commensurable objectives. SPEA combined several features of previous multi-objective evolutionary algorithms in a unique manner. SPEA stored non dominated solutions externally in another continuously-updated population and used a hierarchical clustering algorithm to provide the decision maker with a manageable pareto optimal set. SPEA was applied to a 20 node network as well as to large size networks ranging from 50-200 nodes. The results demonstrated the capabilities of the approach to generate true and well distributed pareto-optimal non dominated solutions. The performance of the SPEA had been compared with the weighted sum method. The results obtained by SPEA were superior to weighted sum method and also it had found all the possible solutions in a single run, thus saving execution time. SPEA was applied to networks of various sizes and it was clear that the algorithm performed well in large network sizes too.
2.1.2 LINEAR PROGRAMMING FOR FUZZY SHORTEST PATH
JingRungYu and TzuHaoWei [32] have proposed a simple linear multiple objective programming to deal with the fuzzy shortest path problem. This approach did not need to declare 0-1 variables to solve the fuzzy shortest path problem because it met the requirements of the network linear programming restraints. Therefore, the linear programming relaxation was used to arrive at an integer solution without using the Branch and Bound technique, and the complexity of the method was reduced. A compromising non-dominated integer optimal solution, the fuzzy shortest path, could be obtained easily without adding extra constraints. The approach not only obtained a fuzzy shortest path but also reduced the complexity of solving the basic fuzzy shortest path problem without using 0-1 variables. This approach not only offered a shortest path but also reduced the complexity of solving the basic fuzzy shortest path formulation. The shortest path problem was just one type of network problems, which also included the minimum spanning tree problem, minimum cost flow problem, and maximum flow problem. They intended to solve other network problems by adopting the linear multiple objective programming approaches and reduced the complexity by reformulating the problem into the type that naturally had integer optima.
M.B. Aryanezhad and E. Roghanian [36] have presented a bi-level linear multi-objective decision making model with interval coefficients for supply chain coordination. Bi-level programming was a tool for modeling decentralized decisions. It consists of the objective(s) of the leader at its first level and that is of the follower at the second level. Three level programming produced results when second level was itself a bi-level programming. By extending this idea it was possible to define multi level programs with any number of levels. Supply chain planning problems were concerned with synchronizing and optimizing multiple activities involved in the enterprise, from the beginning of the process, such as procurement of the raw materials, through a series of process operations, to the end, such as distribution of the final product to customers. Enterprise wide supply chain planning problems naturally exhibited a multi-level decision network structure, where for example, one level correspond to a local plant Control/ scheduling/ planning problem and another level to a corresponding plant wide planning/ network problem. Such a multi level decision network structure was mathematically represented by using "multi-level programming" principles. It studied a "bi-level linear multi-objective decision making" model in with "interval" parameters and presented a solution method for solving it. This method used the concepts of tolerance membership function and multi-objective multi-level optimization when all parameters were imprecise and interval.
Mahdavi et al. [74] have proposed algorithms for bi objective shortest path problems in fuzzy networks. It considered the bi objective shortest path problem (BSP) in fuzzy networks and developed three algorithms for solving the problem. It presented two labeling type algorithms for finding non dominated paths from a specified node to every other node. Since the number of non dominated paths may be large, choosing a preferred path was required. Thus, it utilized a distance function for comparison of fuzzy numbers in a fuzzy ranking method to rank the obtained non dominated paths according to the first objective, the second objective or both. It then presented a procedure for computing the non dominated paths requiring less computing time. The third algorithm was based on a dynamic programming approach. For this algorithm, presented an approach for converting the two fuzzy numbers corresponding to the two objectives into a single number for comparison purposes. The dynamic programming algorithm for the single objective case and the distance method for ranking fuzzy numbers were adaptively used in the proposed algorithm. The algorithm computed one shortest path, as an alternative solution to several non dominated paths. Examples were worked out to show the effectiveness of the proposed algorithms.
2.1.3 MULTI CRITERIA APPROACH
Zbigniew Tara Pata [33] has presented selected multi criteria (multi objective) approaches to shortest path problems. A classification of multi objective shortest path (MOSP) problems was given. Different models of multi objective shortest path problems were discussed in detail. Methods of solving the devised optimization problems were presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multi objective shortest path problems were described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi weighted graph problems (using modified Dijkstra's algorithm) was given. Experimental results of using the presented methods for multi criteria path selection in a terrain-based grid network were given.
Milan Stanojevi´c et al. [35] have presented the number of efficient points in criteria space of multiple objective combinatorial optimization problems. The number of Pareto optimal solutions grown exponentially with the problem size. It was concluded that under certain assumptions, which were reasonable and applicable in the majority of practical problems, the number of efficient points had grown polynomially. Experimental results with the shortest path problem, the Steiner tree problem on graphs and the traveling salesman problem showed that the number of efficient points were even much lower than the polynomial upper bound. In all the considerations it was assumed that criteria were not correlated. On the other hand, the number of efficient points had decreased with the increase of correlation between criteria. Since it was known that between many criteria used in practice correlation exists (the length, time and price of path, price and reliability etc.), it also expected even less number of efficient points when it had come for the practical problems.
Ilias Diakonikolas and Mihalis Yannakakis [40] have investigated the problem of computing a minimum set of solutions that approximates within a specified accuracy the Pareto curve of a multi objective optimization problem. They showed that for a broad class of bi-objective problems (containing many important widely studied problems such as spanning tree, shortest paths, matching and many others), they computed in polynomial time an Pareto set that contained at most twice as many solutions as the minimum such set. Furthermore they showed that the factor of 2 is tight for these problems, i.e., it was NP-hard to do better. They presented upper and lower bounds for three or more objectives, as well as for the dual problem of computing a specified number k of solutions which provided a good approximation to the Pareto curve.
Mir Mozaffar Masoumi et al. [51] have concerned with a particular multi criteria optimal path problem, known as the multi-objective shortest path problem. The purpose was to study a data envelopment analysis (DEA) model that allowed determining the set of all non-dominated paths on a network. They discovered which DEA model's solutions correspond to the Pareto optimal solution of a MSPP. Also, they have explained by The VRS FDH model without output that the non-dominated paths obtained by label-setting Martins' algorithm were equivalent to the efficient DMUs in DEA environment. The DEA technique provided powerful vision to peruse other multi-criteria optimal path problems, which had not been solved by an efficient labeling algorithm, in which both kinds of criteria, costs and benefits exist on each arc. Here it was considered costs as inputs and benefits as outputs, and was also able to solve multi criteria optimal path problems. They proved that the non-dominated path in multi objective shortest path problem was equivalent to corresponding strongly efficient unit in its DEA model without output with actually observed units.
2.1.4 NEW GENERIC METHOD
George Tsaggouris and Christos Zaroliagis [39] have provided an improved FPTAS for multi objective shortest paths a fundamental (NP-hard) problem in multi objective optimization along with a new generic method for obtaining FPTAS to any multi objective optimization problem with non-linear objectives. They showed how these results could be used to obtain better approximate solutions to three related problems, multi objective constrained [optimal] path and non-additive shortest path that have important applications in QOS routing and in traffic optimization. They also showed how to obtain a FPTAS to a natural generalization of the weighted multi commodity flow problem with elastic demands and values that models several realistic scenarios in transportation and communication networks.
2.1.5 DYNAMIC PROGRAMMING FOR KNAPSACK PROBLEM
Cristina Bazgan et al. [38] have presented an approach based on dynamic programming, for solving the 0/1 multi objective knapsack problem. The main idea of the approach relied on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, they obtained an efficient method that outperformed the existing methods both in terms of CPU time and size of solved instances. Considerable numerical experiments on various types of instances were reported. A comparison with other exact methods was also performed. In addition, for the first time to the knowledge, they presented experiments in the three-objective case.
2.1.6 MARTIN'S LABEL SETTING ALGORITHM
S. Ismail Mohideen and B.Rajesh [49] have presented two set of objectives, one with triangular fuzzy number as edge weights and another with a three objective shortest path problem for MOSPP. When those two sets were solved using Martin's label setting algorithm, to find the non dominated solutions, it concluded that the number of non dominated solutions was less for the multi objective shortest path problem with objectives as triangular fuzzy number, when compared to three objective shortest path problems. The result also holds true, when those two set of objectives were solved using other multi objective shortest path algorithm like Yen's algorithm and Corley and Moon algorithm.
K.Karthikeyan [62] has presented a comparative study of multi objective shortest path problems. For a multi objective shortest path problem (MOSPP) of a network, there were several Pareto optimal solutions. The decision maker selected the best one or the most satisfactory solution depending on the priority and nature of the problem. In this they used the concept of Properly Pareto optimal solution for MOSSP and proved that it was stronger than Pareto optimal solution using Geoffrion's approach which is an extension of martin label setting algorithm by means of an example.
2.1.7 POLYNOMIAL TIME ALGORITHM
Lucie Galand et al. [50] have studied Choquet based optimization when the capacity used to parameterize the Choquet integral was concave and the disutility was convex. They have presented various algorithms to compute Choquet optimal solutions in multi objective minimal spanning tree and shortest path problems. All of them relied on the use of a default approximation bounding Choquet expected disutilities. The potential use of the bound have introduced in this was not restricted to Choquet optimal shortest path or spanning tree problems. As soon as a polynomial time algorithm was known for the standard version of a combinatorial problem, Proposition 1 provided a polynomially computable bound that used for the search of a Choquet optimal solution in the multi objective version. This bound can either be used in a branch and bound procedure or in a ranking approach, the latter requiring ancient k-best solution procedure.
Andras Gyorgy et al. [30] have presented the On-Line Shortest Path Problem under Partial Monitoring. The on-line shortest path problem was considered under various models of biased monitoring. Given a directed weighted acyclic graph whose edge weights can change in an arbitrary way, a decision maker has to select in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defined as the sum of the weights of its composing edges)be as small as possible. In generalizing the multi-armed bandit problem, after selecting a path, the decision maker learned only the weights of those edges that belonged to the chosen path. For this problem, an algorithm was given whose average cumulative loss in n rounds exceeded that of the best path, matched off line to the complete sequence of the edge weights, by a quantity and depends only polynomially on the number of edges of the graph. The algorithm was implemented with complexity that was linear in the number of rounds n (i.e., the average complexity per round is constant) and in the number of edges. An extension to the so called efficient label setting was also given, in which the decision maker was informed about the weights of the edges corresponding to the chosen path. Another extension was shown where the decision maker competed against a time varying path, a generalization of the problem of tracking the best proficient. A version of the multi armed bandit setting for shortest path was also discussed. where the decision maker learned only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results were also presented.
2.1.8 MULTI OBJECTIVE OPTIMIZATION
Christina M. Young et al. [54] have proposed Multi objective Optimization of a Port-of-Entry Inspection Policy. At the port-of-entry, containers were inspected through a specific sequence of sensor stations to detect the presence of biological, chemical agents and radioactive materials, and other unlawful shipment. The checkup policy, which included the sequence in which sensors were applied and the threshold levels used at the inspection stations, affected the probability of misclassifying a container as well as the cost and time spent in inspection. This work was an extension of Elsayed et al., which considered an inspection system operating with a Boolean decision function combining station results. In this, they presented a multi objective optimization approach to determine the optimal sensor arrangement and threshold levels, while considering time and cost. The total cost included cost incurred by misclassification errors and the total expected cost of inspection, while the time represented the total expected time a container spends in the investigation system. Examples which apply the approach in different systems were presented
2.1.9 CONSTRAINED PROGRAMMING TECHNIQUE AND WEIGHTED SUM METHOD
S.K. Roy and D.R. Mahapatra [68] have presented with the interval coefficients to the multi-objective stochastic transportation problem. They concentrated on our attention to multi-objective stochastic transportation problem involving an inequality type of constraints in which all parameters ( supply and demand ) were log-normal random variables and the coefficients of the objectives were interval numbers. The minimization interval valued multi-objective transportation problem was also converted in optimization of bi objective functions using the order relation which represented the decision makers preference between the interval costs had been defined by the right limits, left limits, the center and the width of an interval. At first they converted the proposed probabilistic constraints into an equivalent deterministic constraints by chance constrained programming technique. Then the equivalent transformed problem of original multi-objective transportation problem had been solved by the weighted sum method and they obtained the optimal compromise solution. Lastly a numerical example was provided for the sake of illustrate the methodology.
2.1.10 ANT COLONY OPTIMIZATION
Dilpreet kaur and Dr.P.S Mundra [79] have presented Ant Colony Optimization, a technique used for finding shortest path. Ant colony optimization technique was used to find the shortest path finding algorithm in spite of GPS or any other method. Their motive was to compare the time and accuracy with the old algorithms with the proposed algorithm using ant colony optimization. It is used for searching and scanning the shortest path in between two points selected randomly by the user. The algorithm was basically designed for edge detection but here it was implemented to find the path through hurdles. Ant colony optimization (ACO) was a class of optimization algorithms modeled on the actions of an ant colony. ACO methods were useful in problems that need to find paths to goals. It Formed a zigzag track which was randomly generated by the algorithm every time implemented. Arena which was randomly created had white pixels showing clear area and black one for restricted entry. It presented the average time taken by the algorithm and the accuracy for the same to build a chat. The main aim was to pass through environment in secure form and to avoid obstacles. Examples of this were autonomous robots on distant planets without the possibility to be controlled in real time because of latencies in signal sending, or automatic vehicles control. Another example of path-finding was strategic computer games, mostly with computer opponent. Path finding was also widely used in finding best routers interconnection for data transmission in many kinds of computer networks, some user friendly visualization of results of path finding, which was realized by application of computer graphic techniques had also seen. A geographical information system (GIS) was software and geographical data designed for effective gathering, retaining, editing another, was called routing
Dilpreet Kaur and Dr.P.S Mundra [84] have presented shortest path finder in real time application. Ant colony optimization (ACO) was a class of optimization algorithms modeled on the actions of an ant colony. ACO methods were useful in problems that need to find paths to goals. Artificial 'ants' simulation agents located optimal solutions by moving through a parameter space representing all possible solutions. The basic idea in ant colony optimization algorithms (ACO) was to imitate the cooperative behavior of real ants to solve optimization problems. ACO Meta heuristics had been proposed by M. Dorigo. They had been seen as multi agent systems in which each single agent is inspired by the behavior of a real ant. Traditionally, ACO had been applied to combinatorial optimization problems and they had achieved widespread success in solving different problems. The main interest of real ant's behavior was simple ants using collective behavior perform complex tasks such as transportation of food and finding shortest paths to the food sources. ACO algorithms simulate the principle that using very simple communication mechanism, an ant colony was able to find the shortest path between two points. The purpose of this method was to design a robot controller which was able to pursue a given goal with obstacle-avoiding capability in which the two tasks, i.e. aiming at the target and avoiding obstacles, solving the problem was performed. For a given ROBOT, the path was chosen according to the obstacles coming the way. When facing an obstacle, there was an equal probability for every robot to choose the left or right path.
2.1.11 LINK BASED SHORTEST PATH ALGORITHM
Yongtaek LIM And Hyunmyung KIM [28] have proposed a new shortest path algorithm called link based shortest path algorithm, adequate for considering path overlap and turn prohibitions and tested, which provided efficient dissimilar alternative paths. This algorithm build paths based on the degree of overlapping ratio and did not need network expansion to find the shortest path because it searched the paths with link-end cost, not node cost. After verifications of the algorithm with some examples, they also expanded it to dynamic one and tested. From the observed results of some numerical examples, they concluded that the algorithm was more efficient for finding several dissimilar shortest paths than others. The algorithm proposed was applied to a variety of network analyses. In first, it could be adopted in the field of travel information such as providing diverse routes for drivers. Secondly, the algorithm generated dissimilar paths so that it could alleviate the problem of IIA (Independence of Irrelevant Alternatives) in log it type stochastic assignment. Lastly, it can be also used for solving easily multi-mode traffic assignment, which should consider transfer behaviors of users.
2.1.12 DYNAMIC SHORTEST-PATH ALGORITHM
Luciana S. Buriol et al. [37] have proposed Speeding up Dynamic Shortest-Path Algorithms. Dynamic shortest-path algorithms updated the shortest paths taking into account a change in an arc weight. It had described a new generic technique that allowed the reduction of heap sizes used by several dynamic single-destination shortest-path algorithms. For unit weight changes, the updates were done without heaps. Those reductions almost always reduced the computational times for these algorithms. In computational checking, several dynamic shortest-path algorithms with and without the heap-reduction technique were compared. Speedups of up to a factor of 1.8 were observed using the heap reduction technique on random weight changes and of over a factor of five on unit weight changes. It was compared as well with Dijkstra's algorithm, which recomputed the paths from scratch. With respect to Dijkstra's algorithm, expedite up to five orders of magnitude were observed.
Udaya Kumar Reddy K. R and K. Viswanathan Iyer [41] have presented all-pairs shortest-paths problem for unweighted graphs in O (n2 log n) time. Given a simple connected unweighted undirected graph G = (V (G), E (G)) with |V (G)| = n and |E (G)| = m, they presented a new algorithm for the all pairs shortest path (APSP) problem. The running time of the algorithm was in O (n2 log n). This bound was an improvement over previous best known O (n2.376) time bound of Raimund Seidel for general graphs. The algorithm presented did not rely on fast matrix multiplication. The algorithm with slight modifications, enabled to compute the APSP problem for un weighted directed graph in time O(n2 log n), improving a previous best known O (n2.575) time bound of Uri Zwick.
Farrukh Shehzad and Muhammad Akbar Ali Shah [43] have proposed Evaluation of Shortest Paths in Road Network. Finding the shortest path was a central task in many network and transportation analysis problems. The main reasons were many of the optimization problems could be formulated as networks and it was usually be the essential part of more complicated transportation analysis problems. Considerable research had been done to develop the faster algorithms for solving this problem and of course, there had been numerous algorithms like Bellman-Ford-Moore algorithm, Dijkstra algorithm etc. Moreover, some important evaluations have also made to test the efficiency of these algorithms. Unfortunately these evaluations were usually based on randomly generated networks which cannot reflect the characteristics of real road networks that were concerned. Zhan and Noon and Shad et al. had evaluated the shortest path algorithms using real road networks. However, these evaluations are quite meritorious in their class. The choice of Dijkstra algorithm was due to its characteristic of running just on non-negative arc length, solving all the subtypes of single-source shortest path problem and taking any of the nodes as source. Its modification also justify Bellman's principal of optimality that shortest path has the shortest sub-paths. The second algorithm, Floyd Warshall algorithm, was also most generally used to find the shortest distance from any node to any other node in networks. Finally the results of the study were a guideline not only for passengers who travel by roads but also for transporters and for the companies that spend a lot on road transportation. Government agencies such as Highway Department also used this methodology to prioritize its limited budget to construct certain routes in order to best utilize the scare national resources. James B. Orlin and Kamesh Madduri [55] have presented A Faster Algorithm for the Single Source Shortest Path Problem with Few Distinct Positive Lengths. They proposed an efficient method for implementing Dijkstra's algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges had positive length, and where there were few distinct edge lengths. The SSSPP was one of the most widely studied problems in theoretical computer science and operations research. On a graph with i vertices, j edges and K distinct edge lengths, our algorithm runs in O (m) time. They tested the algorithm against some of the fastest algorithms for SSSPP on arbitrarily (but positively) lengthen graphs. The experiments on graphs with few edge lengths confirmed our theoretical results, as the introduced algorithm consistently dominated the other SSSPP algorithms, which did not achieve the special structure of having few distinct edge lengths.
Yanfang Deng and Hengqing Tong [73] have proposed dynamic shortest path algorithm in stochastic traffic networks using PSO based on fluid neural network. In this, a new method was proposed for solving the shortest path problem in stochastic traffic networks. The approach was based on combining FNN model with PSO. The PSO search used a modified indirect path-encoding scheme. The algorithm was simple and easy and could find quickly the shortest path without falling into local minimums, which occurred if energy function was used to solve the same problem. Since PSO and FNN were all parallel algorithms, it was very easy to run the new algorithm on parallel computer or even on neural computer, which reduced the computational time drastically. The parameter of PSO algorithm is further optimized by chaotic operator for diversity of particle in order to further enhance the convergence time of the algorithm.
2.1.13 SIMPLEX ALGORITHM
Abdallah W. Aboutahoun [92] has proposed minimum cost-reliability ratio path problem. The problem of finding a minimal cost-reliability ratio path was considered. The optimal solution to this problem was shown to map into an extreme supported non-dominated objective point in the objective space of the bi objective shortest path problem. Different forms of reliability were presented. It was assumed that this reliability does not change over time. It employed a parametric network simplex algorithm to compute all extreme supported non-dominated objective points. An adequacy conditions introduced by Ahuja were used to reduce the path enumeration. The algorithm was based on the method of Sedeno Noda and Gonzlez Martín. A numerical example was provided to illustrate the algorithm.
2.2 CLASSIFICATION OF JOB SEQUENCING ALGORITHMS
There were various algorithms for solving job sequencing problems. Some of the algorithms are explained below.
2.2.1 TABU SEARCH ALGORITHM
Eugeniusz Nowicki and CzeslAw Smutnicki [26] have proposed an advanced tabu search algorithm for the job shop problem. The job shop scheduling problem with the makespan criterion was a certain NP-hard case from OR theory that had excellent practical applications. This problem, had been observed for years, is also regarded as an index of the quality of advanced scheduling algorithms. It provided a new approximate algorithm that was based on the big valley phenomenon, and used some elements of so-called path re linking technique as well as new theoretical properties of neighborhoods. The algorithm thus provided a powerful tool to solve the job shop problem with the makespan criterion. It offered very good accuracy, in comparison with the other best known approaches, obtainable in a short running time on a modern PC. Those properties, confirmed through exhaustive tests on all known benchmarks, followed from the suitable use of properties of the solution space, especially BV. The general idea of the algorithm could be applied to other scheduling problems, as an example, the flow shop and hybrid flow shop problem.
2.2.2 FUZZY TOPSIS METHOD
Pragati Jain and Manisha Jain [63] have presented Fuzzy TOPSIS Method in Job Sequencing Problems on machines of unequal efficiencies. Sequencing problems arise when there was a choice as to the order in which a number of tasks can be performed. In such problems, they determined an appropriate order or sequence for a series of jobs to be done on a finite number of service facilities. They presented the way of making sequence of a finite number of jobs on a finite number of machines of unequal efficiencies by using the technique of order preference by similarity to ideal solution or simply TOPSIS Method in fuzzy environment. The order of machines was random. The time taken by the machines for conducting jobs was assumed as imprecise processing time or fuzzy numbers. The fuzzy evaluation values were given by triangular fuzzy numbers. Weights were given to each machine according to their efficiency. A new distance was defined using which the distance of each job from the positive and negative ideal solutions were calculated. Finally a closeness coefficient was defined and that determined the ranking order of the jobs so that the complete project got finished at minimum time-span. A numerical example demonstrated the computational process of the projected model.
2.2.3 PAYOFF SYSTEM
Joss S anchez Perez [69] has proposed a modification to the concept of the potential of Hart and MasColell to determine a payoff system for job scheduling problems. They obtained explicit formulas for the potential of job scheduling problems and for its corresponding payoff system. Also established a relation between this payoff system and the Shapley value of a certain cooperative game.
2.2.4 GENETIC ALGORITHM
Sayedmohammadreza Vaghefinezhad and Kuan Yew Wong [77] have presented a Genetic Algorithm Approach for Solving a Flexible Job Shop Scheduling Problem .Flexible job shop scheduling had been noticed as an effective manufacturing system to cope with rapid development in today's competitive environment. Flexible job shop scheduling problem (FJSSP) is known as a NP-hard problem in the field of optimization. Contemplate the dynamic state of the real world makes this problem more and more complicated. Most studies in the field of FJSSP had only focused on minimizing the total makespan. In this, a mathematical model for FJSSP had been developed. The objective function was maximizing the total profit while meeting some restraints. Time varying raw material costs and selling prices and dissimilar demands for each period, had been considered to decrease gaps between reality and the model. A manufacturer that produced various parts of gas valves had been used as a case study. Its scheduling problem for multi-period, multi-part, and multi-operation with parallel machines had been solved by using genetic algorithm (GA). The best obtained answer determined the economic amount of production by different machines that belonged to predefined operations for each part to satisfy customer demand in each period.
Surekha P and S.Sumathi [57] have presented a genetic algorithm and ant colony optimization algorithm for solving the Job-shop Scheduling Problem (JSSP).The genetic algorithm comprised of different stages like generating the initial population, choosing the individuals for reproduction and reproducing new individuals. Ant Colony Optimization (ACO) was a Meta heuristic inspired by the foraging behavior of ants, which was also used to solve this combinatorial optimization problem. In JSSP ants moved from one machine (nest) to another machine (food source) depending upon the job flow, there by optimizing the sequence of jobs. The sequence of jobs was scheduled using Fuzzy logic and optimizes using GA and ACO. The makespan and its efficiency, completing time, algorithmic efficiency and the elapsed time for the genetic algorithm and the ant colony algorithm were evaluated and compared. The improvement in the performance of the algorithms based on the computed parameters was also discussed. Computational results of those optimization algorithms were compared by analyzing the JSSP bench mark instances, FT10 and the ABZ10 problems.
2.2.5 JOHNSON'S SEQUENCING RULE
Punit Kumar Singh and Dr. Rakesh Kumar [78] have presented path optimization algorithm for network problems using job sequencing technique .The job sequencing technique was used to determine an optimal sequence. It performed a series of jobs by a number of specific orders so that it calculated the optimal cost. They proposed a novel approach to find an optimal path from source to destination by taking advantage of job sequencing technique. They had used n jobs m machine sequencing technique and this was divided into n jobs 2 machine problems. Using Johnson's sequencing rule, they solved the problem and obtained the (n-1) sub sequences of the route. Using the proposed algorithm, they calculated the optimal sequence, which lead to the shortest path of the network.
2.2.6 MILP APPROACH
Christodoulos A. Floudas, Xiaoxia Lin [27] have presented the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. They focused on the short-term scheduling of general network represented processes. First, the different mathematical models that had been proposed in the literature were classified mainly based on the time representation. Continuous and Discrete time models were presented along
with their strengths and limitations. Several classes of approaches for enhancing the computational efficiency in the solution of MILP problems were discussed. Furthermore, a summary of computational experiences and applications wais provided. They concluded with perspectives on future research directions for MILP based process scheduling technologies.
2.2.7 SETUP TIME METHOD
Dr.Khallel Ibrahim Mahmoud and Israr Ahmad [42] have presented Job-Shop Sequencing Real Life Problem with Setup Time. They analyzed the sequencing situations on two machines where the machine setup time was not independent of processing order. A real case study of Hadhramout Industrial Company Complex, Mukalla, Yemen was taken as a model. Data was collected and analyzed using MS-Excel by different methods. The problem formulation had been presented. Several solutions were obtained by applying sequencing methods. The comparison of different solutions was done to choose the optimal solution. The time was reduced by 23% to perform the group of jobs and the setup time was reduced 30.5% as well as the mean flow time was reduced by 30.5%.
2.2.8 MATHEMATICAL MODEL
Jafar Razmi et al. [45] have proposed a Mathematical Model for a Flow Shop Scheduling Problem with Fuzzy Processing Times. Various methods have been developed by considering special conditions. Thus, most of these studies were concentrated on non-exact solutions. In addition, non-deterministic problems were analyzed by fuzzy logic. Some of other studies on stochastic flow shop scheduling problem were also addressed. In this, they considered the fuzzy flow shop scheduling problem. The optimal probability was defined similar to the definition of the optimal index of the stochastic model. The criterion of a better solution selection was the possibility of priority of one sequence to other sequences of the last step. This research had proposed a method to estimate the distribution function of the makespan by using fuzzy numbers and defined the feasibility of the provided solution through this method.
2.2.9 MULTI OBJECTIVE ARTIFICIAL IMMUNE ALGORITHM
Zohreh Davarzani et al. [82] have proposed multi objective artificial immune algorithm for flexible job shop scheduling problem. Flexible job shop scheduling was very important in production management and combinatorial optimization. It was a NP-hard problem and consisted of two sub problems, sequencing and assignment. Multi objective Flexible Job-Shop Scheduling Problems (MFJSSP) was formulated as three-objective problem which minimized completion time (makespan), critical machine workload and total work load of all machines. In this, a Multi objective Artificial Immune Algorithm (MAIA) for FJSSP was presented. The algorithm had increased the speed of convergence and diversity of population. Kacem and Bradimart data were used to evaluate the effectiveness of MAIA. The experimental results showed a better performance in comparison to other approaches.
2.3 CLASSIFICATION OF LINEAR PROGRAMMING ALGORITHMS
There were various algorithms for solving linear programming problems. Some of the algorithms are explained as follows.
2.3.1 MATHEMATICAL FORMULATION
Samir A. Abass [52] has proposed a mathematical formulation of bi-level linear programming problem to deal with an interval number programming approach. Bi-level linear programming problem was usually viewed as a problem with two decision makers at two different hierarchical levels. The upper level decision maker called the leader, selects his or her decision vector first and the lower decision maker called the follower, selects his or her afterward based on the decisions of the upper level. In mathematical programming problem, the coefficients in the objective function and the constraint functions were always determined as crisp values. In practice, however, there were many decision situations where the objective functions and/or the constraints were uncertain to some degree. Over the last two decades, interval programming based on the interval analysis had been developed as a useful and simple method to deal with this type of uncertainty. The interval numbers were in both of the objective function and the constraints. An Illustrative numerical example was provided to clarify the proposed approach.
2.3.2 SOLUTION ALGORITHM
Omar M. Saad et al. [53] have presented a solution algorithm that had been proposed to solve fuzzy integer linear fractional programs (FILFPP). Some fuzzy concepts had been given to convert problem (FILFPP) to a no fuzzy version and the Charnes & Cooper transformations had been used to complete the solution process. Summarizing, many aspects and general questions remained to be studied and explored in the area of fuzzy integer linear fractional programming. Despite the limitations, they believed that this was an attempt to establish underlying results which hopefully helped others to answer of the questions. There were however several open points for future research in the area of (FILFPP).
2.3.3 HYBRID HEURISTIC ALGORITHM
Krasimira Genova [65] has presented a hybrid heuristic algorithm, which used procedures for search of feasible integer directions with one or two nonzero components and linear optimization. The algorithm was iterative and it combined constructive and locally improved strategies for finding a new current solution. A subsequence of sub problems was solved, aimed at seeking a feasible solution of the general Mixed Integer Problem (MIP), after which the feasible solution found was improved with respect to the problem objective function. The algorithm was characterized by polynomial time computing complexity.
Krasimira Genova and Vassil Guliashki [66] have presented a survey of methods and approaches solving linear integer problems, developed during the last 50 years. A large variety of different real life problems in practice were formulated as integer optimization problems. Their number and their size increased continuously. Regardless of the fact, that the productivity of exact algorithms designed to solve integer problems had been considerably improved during the last years, very often they were not be applied to solve practical problems of middle and large size because of their excessive runtimes and memory requirements. The published theoretical and also algorithmic investigations were devoted to combinatorial or binary problems. As a result, the most wide spread heuristic procedures for obtaining suitable initial solutions, evaluations of candidate solutions, cutting planes, specialized search strategies, etc., integrated in the commercial programming products, were effective for problems with 0-1 variables or for problems having a special structure. The solution of the integer problem in the general case remained considerably harder. The hybrid methods were promising tools, since they combined the best features of different methods (exact techniques or Meta heuristics) in a complementary mode. Those problems belonged to the class of NP-hard optimization problems. To determine exact optimal solutions for this class of problems it required the use of considerable computational resources. The development of effective hybrid methods, combining in a suitable way the best features of different approaches (exact or approximate) was the actual direction, in which many researchers devoted their efforts to solve successfully various hard practical problems. Many large size real problems were not solved by exact algorithms due to their exponential computational complexity. In such case the only way was to use the approximate polynomial time algorithms.
2.3.4 FUZZY DECISIVE SET METHOD
C. Veeramani et al. [67] have presented fuzzy multi-objective linear programming problem in which both the resources and the technological coefficients were fuzzy with linear membership function was studied. Further a FMLOP problem was converted into an equivalent crisp non-linear programming problem using the concept of max-min principle. The resultant non-linear programming problem was solved by fuzzy decisive set method. The discussed method was illustrated through an example. The method could be extended to solve problems like FMLOP with triangular or trapezoidal membership function and linear fuzzy fractional programming problems.
2.3.5 EXPONENTIAL BARRIER METHOD
Parwadi Moengin [80] has concerned with the study of the exponential barrier method for linear programming problems with the essential property that each exponential barrier method is concave when viewed as a function of the multiplier.. It presented some background of the method and its variants for the problem. Under definite assumption on the parameters of the exponential barrier function, they gave a rule for choosing the parameters of the barrier function. Algorithms and theorems for the methods were also given.
2.3.6 INTERVAL VALUED PROGRAMMING APPROACH
Mousumi Kumar and Bijay Baran Pal [85] have presented an interval valued goal programming approach for solving multi objective fractional programming problems. In the model conception of the problem, the interval valued system constraints were converted in to equivalent crunchy system. The interval valued fractional objective goals were transformed into linear goals by employing the iterative parametric method which was an extension of Dinkelbach approach. In the solution process, the target achievement function, termed as 'regret function', was formulated for minimizing the unwanted deviational variables to achieve the goals in their specified ranges and thereby arriving at most satisfactory solution in the decision making environment.
Sohrab Effati and Morteza Pakdaman [89] have introduced an interval valued linear fractional programming problem (IVLFP). An IVLFP is a linear fractional programming problem with interval coefficients in the objective function. It was proved that it can convert an IVLFP to an optimization problem with interval valued objective function which its bounds were linear fractional functions. Also there was a discussion for the solutions of this kind of optimization problem.
A.Abbasi Molai and E. Khorram [29] have introduced a Satisfaction Function (SF) to compare interval values on the basis of Tseng and Klein's idea. The SF estimated the degree to which arithmetic comparisons between two interval values were satisfied. Then, defined two other functions called Lower and Upper SF based on the SF. Those functions were applied in order to present a new interpretation of inequality constraints with interval coefficients in an interval linear programming problem. This problem was as an extension of the classical linear programming problem to an inaccurate environment. On the basis of definitions of the SF, the lower and upper SF and their properties, they reduced the inequality constraints with interval coefficients in their satisfactory crisp equivalent forms and defined a satisfactory solution to the problem. Finally, a numerical example was given and its results were compared with other approaches.
2.3.7 PARAMETRIC APPROACH
Sanjay Jain and Nitin Arya [88] have proposed an inverse model for linear fractional programming (LFP) problem, where the coefficients in the objective function were adjusted as little as possible so that the given feasible solution x and objective value z becomes optimal. An inverse version of linear fractional programming problem had been studied. The new approach was useful in the situation where the enterprise wanted to work with certain efficiency or wanted to fulfill the sudden market demand with certain efficiency and available resources. This approach was further extended to the nonlinear fractional programming. Here the parametric approach was used for formulating the inverse LFP problem as a linear programming problem. The method had been illustrated by a numerical example also.
Mahmoud A. Abo-Sinna [87] has presented with multi objective bi-level linear programming problems under fuzzy environment. In this method, tentative solutions were obtained and evaluated by using the partial information on preference of the decision makers at each level. The established results concerning the qualitative analysis of some basic notions in parametric linear programming problems were reformulated to study the stability of multi objective bi-level linear programming problems. An algorithm for achieving any subset of the parametric space, which had the same corresponding Pareto optimal solution, was presented. Also, it established the model for the supply demand interaction in the time of electronic commerce (EC). First of all, the study used the individual objectives of both parties as the foundation of the supply demand interaction. Subsequently, it divided the interaction, in the age of electronic commerce, into the following two classifications: (i) Market transactions, with the primary focus on the supply demand relationship in the marketplace; and (ii) Information service, with the primary focus on the provider and the user of information service. By applying the bi-level programming technique of interaction process, the study had developed an analytical process to explain how supply demand interaction achieved a compromise or why the process failed. Finally, a numerical example of information service was provided for the sake of illustration
2.3.8 LINEAR PROGRAMMING MODEL
B. Kareem and A.A.Aderoba [34] have presented Linear Programming based Effective Maintenance and Manpower Planning Strategy a Case Study. Linear Programming (LP) model was formulated based on the outcomes of the analyzed data. The data analyzed included production capacity, maintenance budget, maintenance cycle, and waiting time of production facilities in case of failure. Data were analyzed based on cost of the manpower, machine depreciation cost and the spare part cost, which were considered to be proportion to the number/magnitude of the break downs. The generated Liner Programming model was solved using software named "the Quantitative System for Business- QSB (Version 3.0). The results of the model showed that four maintenance crews were needed to effectively carryout maintenance jobs in the industry. The sensitivity analysis displayed that the results had a wide range of feasibility.
Nezam Mahdavi Amiri et al. [44] have considered two classes of fuzzy linear programming problems: (1) Fuzzy number linear programming (FNLP), and (2) linear programming with trapezoidal fuzzy variables (FVLP) problems. They used the trapezoidal fuzzy numbers and a linear ranking function to describe a fuzzy concept of the basic feasible solutions for both problems. Then used the optimality conditions for the FNLP and the FVLP problems and developed fuzzy primal simplex algorithms for solving these problems. Finally, the solved illustrative examples using the simplex algorithms were presented.
Chang-Chun Lin [46] has presented Comments on a mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem. A mixed integer linear programming formulation of the optimal mean/Value-at-Risk briefcase problem, European Journal of Operational Research in a recent proposal of two linear integer programming models for portfolio optimization using Value at Risk as the measure of risk, claimed that the two complement models are equivalent. This note showed that this claim was only partly true. The second model attempted to minimize the probability of the portfolio return falling below a certain threshold instead of minimizing the Value at uncertainty. However, the discontinuity of real-world probability values makes the second model impractical. An alternative model with Value at uncertainty as the objective was thus proposed.
Calice Olivier Pieume et al. [71] have proposed equivalence between the feasible set of a bi-level multi objective linear programming and the set of efficient points of an artificial set, in order to find an optimal solution. The second approach used a Pareto-filter scheme to find an approximated discrete representation of the efficient set. The second approach had the advantage to keep the multi criteria concept of the upper DM, while the first one used an aggregation process to eliminate the multi-criteria concept for the leader. The research benefitted the development of decision support systems for tackling bi-level multi objective linear optimization problems in the real world
2.3.9 GENERIC INTEGER LINEAR PROGRAMMING FORMULATION
Wan-Yu Lee et al. [47] have presented Generic Integer Linear Programming Formulation for 3D IC Partitioning. The success of 3D IC required novel EDA techniques. Although many EDA techniques be present, this technique focused on 3D IC partitioning, particularly at the architectural level to maximize its benefits. First, logical establishments for 3D IC partitioning problems were derived and then the formulations were transformed into integer linear programs (ILPs). The ILP formulation minimized the usage of vertical interconnects subject to the footprint and power consumption constraints. The flexibility of ILP formulation was demonstrated by extending the generic ILP formulation to support designs with multiple supply voltages. This study proposed an ILP reduction technique to speed up the convergence. Experimental results based on the GSRC norms showed that our approach converges efficiently. Moreover, the approach was flexible and was readily extended to the partitioning problems with variant objectives and constraints, and with different abstract levels, for example, from the architectural level down to the physical level. This flexibility had made the ILP formulations superior alternatives to 3D IC partitioning problems.
Roberto Montemanni [48] has presented Integer Programming Formulations for Maximum Lifetime Broadcasting Problems in Wireless Sensor Networks. The aim was to show that tools like integer linear programming, often regarded as over-theoretical and unrealistic, were indeed suitable frameworks to include the latest advances in energy consumption and communication models in wireless sensor networks. Three models of increasing realism had been presented. Experimental results suggested that integer linear programming was used not only as an effective modeling tool, but also as an efficient solving method for problems of realistic size. A surprising result also indicated that the easiest models to solve (in terms of computation times) were the most realistic ones, suggesting that they should be preferred in general. A speed-up technique, based on the characteristics of the problem, had been discussed and experimentally shown to be effective on many of the problems considered. A practical drawback introduced by the speed up technique had been finally identified and a method to overcome it had been introduced.
2.3.10 AN ALGORITHMIC APPROACH TO MULTI OBJECTIVE FUZZY LINEAR PROGRAMMING PROBLEM
R. Sophia Porchelvi et al. [58] have proposed An Algorithmic Approach to Multi Objective Fuzzy Linear Programming Problem. In this, Multi objective Fuzzy Linear Programming Problem under constraints with fuzzy coefficients was considered. A specific ranking method based on distance between fuzzy numbers was used for developing the ranking algorithm. By the Ranking algorithm, MOFLPP using triangular fuzzy numbers was transformed into MOLPP and then solved by Preemptive optimization method. Again it remained to research MOFLPP with general fuzzy numbers and MOFLPP with fuzziness in objective functions.
P. Senthilkumar and G. Rajendran [56] have presented the Solution of Fuzzy Linear Programming Problem. Fuzzy linear programming problem occurred in many fields such as Mathematical modeling, Control theory and Management sciences, etc. In this they presented a new method for solving fuzzy linear programming with fuzzy variables in parametric form. To identify the optimal solution, it had been proposed that the fuzzy linear programming problem was replaced by two auxiliary crisp linear programming problems. Numerical examples were provided to illustrate the method.
Javad Nematian [91] has proposed a new method for solving a multi-objective linear programming model with fuzzy random variables. In this model, a multi-objective linear programming problem with real variables and fuzzy random coefficients was introduced. Then, a new algorithm was developed to solve the model based on the concepts of mean value of fuzzy random variables, chance-constrained programming and piecewise linear approximation method. Furthermore, a nonlinear programming problem which was obtained by Charnes and Cooper's chance constrained approach had been converted to a mixed integer programming problem by using the piecewise linear approximation method. It also found that the global optimal solution of this nonlinear programming problem was incredibly near to the optimal solution of PLA approach. It considered probability distribution function and the variance effect that had direct effect on optimal solutions and its optimal solution was more confident than other optimal solutions. Furthermore, an illustrative numerical example was also given to clarify the method.
2.3.11 SIMPLEX ALGORITHM
Amit Kumar et al. [61] have proposed Generalized Simplex Algorithm to Solve Fuzzy Linear Programming Problems with Ranking of Generalized Fuzzy Numbers. In this, the shortcomings of an existing method for comparing the generalized fuzzy numbers were pointed out and a new method was proposed for same. Also using the proposed ranking method, a generalized simplex algorithm was proposed for solving a special type of fuzzy linear programming (FLP) problems. To illustrate the proposed algorithm a numerical example was solved and the advantages of the proposed algorithm were discussed. Since the proposed algorithm was a direct extension of classical algorithm so it was very easy to understand and apply the proposed algorithm to find the fuzzy optimal solution of FLP problems occurring in the real life situations.
SeyedHadiNasseri and AliEbrahimnejad [64] have proposed Sensitivity Analysis on Linear programming Problems with Trapezoidal Fuzzy Variables. In the real word, there were any problems which have linear programming models and sometimes it was necessary to formulate these models with parameters of uncertainty. Many numbers from these problems were linear programming problems with fuzzy variables. Some authors considered these problems and have developed various methods for solving these problems. Recently, it was considered linear programming problems with trapezoidal fuzzy data and/or variables and stated a fuzzy simplex algorithm to solve those problems. Moreover, they developed the duality results in fuzzy environment and presented a dual simplex algorithm for solving linear programming problems with trapezoidal fuzzy variables. Here, the authors showed that this presented dual simplex algorithm directly used the primal simplex tableau algorithm tenders the capability for sensitivity (or post optimality) analysis using primal simplex tableaus.
Barkha Sharma and Rajendra Dubey [90] have discussed fuzzy linear programming problem for trapezoidal number with the help of simplex algorithm and crisp linear system of equation using the linear ranking function. They proposed few methods to find the fuzzy optimal solution of fuzzy programming problem. Here row reduced echelon form of matrices was used to construct a new method for solving FLPP and Fuzzy simplex algorithms for solving fuzzy number linear programming and also used the general linear ranking functions on fuzzy numbers. The methods were very easy to understand and to apply for fully fuzzy linear system occurring in real life situation as compared to the existing methods. A numerical example was solved to illustrate the method and the obtained results were discussed.
2.3.12 POLYNOMIAL BARRIER METHOD
Parwadi Moengin [72] has proposed Polynomial Barrier Method for Solving Linear Programming Problems. It had described the barrier functions with barrier terms in polynomial order for solving linear programming problems with the essential property that each member was concave polynomial order even when viewed as a function of the multiplier. Under certain assumption on the parameters of the barrier function, it had given a rule for choosing the parameters of the barrier function. The algorithms for those methods were also given in this. The Algorithm was used to solve the problem. It also noted the important thing of those methods which did not need an interior point assumption.
2.3.13 DNA APPROACH
S.Mohanambal et al. [75] have proposed a design and solving LPP method for bina
