{'fraction_non_alphanumeric': 0.02030712427624402, 'fraction_numerical': 0.003272635730469078, 'mean_word_length': 4.765844218674407, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
META-HEURISTIC PROCEDURE TO FIND THE SOLUTION OF JOB SHOP SCEDULING PROBLEM

In most production environment, there is a requirement for effective use of the available resources. Job Shop Scheduling Problem (JSSP) because of its key impact on revenues is at the crux of production planning, of late also known as Enterprise Resource Planning (ERP). Industrial tasks ranging from assembling cars to scheduling airplane maintenance crews are easily modeled as instances of JSSP, and improving solutions by even as little as one percent can have a significant financial impact. Efforts have been put to find not necessarily an optimal solution, but a good one to solve these problems. Tabu Search (TS) is an effective local search algorithm for the JSSP, but the quality of the best solution found depends on the initial solution used. The motivation behind such a paper is to layout critical discussion on the Tabu Search technique for JSSP, based on neighborhood structures for finding initial solutions, in order to better serve the needs of manufacturing community trying to apply Tabu Search technique on their problems. In this paper a approach is presented that uses a different methods, that either single scheduling or double scheduling, with functions of neighborhood selection in Tabu Search Method. The approach is tested on a set of standards instances taken from the literature and compared with other approaches. The computation results validate some effectiveness of the proposed algorithm.


I. INTRODUCTION
Scheduling of resource in any economic setting is of great importance, and yet a computationally difficult and complex process. The origin of Job Shop Scheduling problem (JSSP) is to utilize the available resources as efficiently as possible in manufacturing environments. The Job Shop Scheduling Problem is a very important practical problem. Dimitri Golenko et al. (1995) stated Job Shop Scheduling Problem as, there are j jobs and m machines, each job comprises a set of operations which must be done on different machines for different specified processing times, in a given job dependent order. Efficient methods of solving it will have an important effect on profitability and product quality. But Job Shop Scheduling Problem is among the worst members of the class of NP-hard Problems which has many practical implications. Ouelhadj D (2003) mentioned best examples which are Production system and also optimization of the part of a steel work (any thing considered).
F. Glover (1989) and Moraglio et al. (2004) have defined Tabu Search (TS) in their studies as a local search method designed to find a near-optimal solution of combinatorial optimization problems. The oddity of Tabu Search is a short-term memory used to keep track of forbidden (tabu) recent solutions, thus allowing the search to escape from local optima. Taillard E. (1994) and Nowicki, E. et al. (1996) mentioned that Tabu Search has revealed to be an effective local search algorithm for the Job Shop Scheduling Problem. The aim of this paper is to show the combined use of different neighborhood functions with two different methods that are Single scheduling and Double scheduling to get initial solution of Tabu Search in order to solve the Job Shop Scheduling Problem.

II. REPRESENTATION OF JSSP
Take an example of 3X3 Job Shop Scheduling Problem as mention in the TABLE I. The data includes the routine of the job through each machine and the processing time for each operation is mentioned in the parenthesis.
The first number in each column represents the machine Mi on which the operation has to perform.  The nodes N represent the set of operations' node as well as two dummy nodes at the beginning (source node, U) and the end (sink node, V) of schedule. The weight of each node is the processing time for each operation. The source node and the sink node have zero processing time. The conjunctive (solid) arcs A represent the routes of each job including arcs connecting the source node to the first operation node and the last operation to the sink node. These The disjunctive (broken) arcs B refer to operation that belong to the different job but have to be processed on the same machine. Starting at some initial feasible solution, its neighborhood is searched for a solution of lower cost. If such a solution is found, the algorithm is continued from there, otherwise a local optimum has been found. Often, the problem remains. The local optima obtained may be of poor quality. Therefore, several variants of iterative improvement have been proposed. The main variants can be divided into threshold algorithms, Tabu Search algorithms, variable depth search algorithms and GA's.
The Tabu Search is a meta-heuristic approach designed to find a near-optimal solution of combinatorial optimization problems. This method suggested by Glover. Tabu Search can be briefly sketched as follows. In tabu Search one selects from a subset of permissible neighbors of the current solution, a solution of minimum cost. In basic Tabu Search a neighbor is permissible if it is not in the 'tabu list' or satisfies a certain 'aspiration criterion'. The tabu list is recalculated on each iteration. It is often implicitly defined in terms of forbidden moves from the current solution to a neighbor. The aspiration criterion expresses possibilities to overrule the tabu status of a neighbor.
The performance of a local search algorithm, both in terms of the quality of solutions, and in the time required to reach them is heavily dependent on the neighborhood structure. Formally, given a solution s a neighborhood is a set N(s) of candidate solutions, which are adjacent to s. This means that if currently examining solution is s the next solution examine will be some s'  N(s

IV. PROPOSED APPROACH
The neighborhood function is the most important part of the tabu search algorithm, as it significantly affects both the running time and the quality of solutions. The neighborhood used in this implementation is one introduced by Dell' Amico et al. (1993), which they call NC. NC is the union of the neighborhoods RNA and NB. NC is connected because NB is, and NC is a smaller neighborhood than NA because each arc examined in NC leads to fewer than 5 possible adjacent moves.
The items placed on the tabu list are the reversed arcs, and a move is considered tabu, if any of its component arcs are tabu. This model is used because, in the case of neighborhoods, which may reverse multiple arcs, making only the move itself tabu would allow many substantively similar moves (i.e. those which share arcs with the tabu move) to be taken.
Single Scheduling is constructive heuristic, which examine a subset of operations and schedule these operations one at a time. These algorithms have the advantage of running in sub-quadratic time and producing reasonable result with any of a number of good priority rules. While Single Scheduling algorithms are no longer considered to be the best for solving large job shop instances, they can still produce good initial solutions for local search algorithms.
Double Scheduling is an extension of the basic single-scheduling framework. This algorithm take two lists in consideration for the first operation and the last operation of each job. The algorithm then alternates between lists, scheduling one operation and updating any necessary data each time, until all operations are scheduled. This algorithm tries to pass up a critical problem with single scheduling algorithms, namely that as they close to completion, most of the operations are scheduled poorly.
Additionally, the proposed double search chooses from the respective lists using a cardinality-based semi-greedy heuristic with parameter c, which means that the priority rule selects an operation uniformly at random from amongst the c operations with the lowest priority. This provides for a greater diversity of initial solutions which means that over several successive runs, a local search algorithm will explore a larger amount of total solution space than would otherwise be possible. In this implementation, the parameter c was set to 3. Fig 3 shows the tabu search in its canonical form. There are two high-level goals for improving the quality of solutions. The first is to attempt to visit nearby improving solutions that would be unreachable. The second goal is to increase the total amount of the solution space the tabu search visits. The former tries to ensure that all nearby local optima are explored to find reasonable solutions quickly. The latter tries to find solutions close to a global optimum by visiting many different areas of the solution space.

The Tabu Search Framework as shown in
One optimization critical to an efficient local search algorithm is the rapid computation of the value of a neighboring solution. Ideally it is possible to perform an exact evaluation quickly, but if this cannot be done, a good estimation will suffice. In the present problem, computing the exact value of the makespan for a neighboring solution is expensive. However, we can find the value of a reasonable estimation in time proportional to the number of arcs reversed by the move. That is, we can compute the value of the longest path through the affected arcs. Another optimization important to the overall running time of a Tabu search algorithm is the implementation of the Tabu list. It is convenient to use this structure as an actual list. Another approach is to store a matrix of all possible operation pairs (i.e. arcs). A time stamp is affixed to an arc when it is introduced into the problem by taking a move, and the time-stamping value is incremented after every move. With this representation, the tabu list may be dynamically resized in constant time.
It is important for a tabu search algorithm to cover as much of the solution space as possible to increase the probability of finding a better solution. One particular problem to overcome is cycling amongst solutions. Visiting the same solutions repeatedly wastes moves that could otherwise be leading the search to unexplored solutions. The tabu list prevents the algorithm from spinning in small, tight cycles by making recently visited solutions tabu. However, this cannot guard against cycles whose length is longer than the tabu list.

V. COMPUTATIONAL RESULTS
The results for the three problems (FT06, FT10, and FT20  The JSSP is to find the sequence of jobs on each machine in order to minimise a given objective function. The objective function most often used is to minimise makespan. The makespan of a schedule can be defined as the time elapsed from the beginning of processing until the last job has finished. Some other objective functions that could be used include tardiness, earliness, and flow time. The difficulty of this problem makes it very hard for conventional search-based methods to find nearoptima in reasonable time. Local search method is defined to solve scheduling problems. One of them is Tabu Search (TS). The basic idea of Tabu search is to explore the search space of feasible scheduling solutions by a sequence of moves and choosing the best available. The elements of Tabu Search are short-term memory, tabu tenure, and aspiration criteria.
This work has demonstrated that it is possible to take existing tabu search algorithms and adjust them to provide reasonable solutions to a wider class of problems. As is evident from the data, the initial solution provided by the double scheduling algorithm is substantially poorer for the instances with sequence dependent setup times than for those instances without them. This is likely because the double scheduling algorithm does nothing to prevent large setup times on the machine arcs connecting the left and right halves. Even so, the Double schedule typically found better initial solutions that those found by the unidirectional single schedule tested.