Job Shop Scheduling Problem

**Introduction**

Scheduling difficulties have in the past decade received increased attention. Scheduling can be labeled as the apportionment of communal resources and this is often done over time as a result of competing activities. Scheduling glitches have been examined from several different angles. More specifically, the Job shop problem has received increased scrutiny and it has turned out to be a very important scheduling problem (Bedoya-Valencia¸ 2007). According to the job shop scheduling, there is a determinate in jobs, and individually of the jobs consists of different sequence processes. There is the existence of predetermined machines, and every machine can be able to be able to process at most one operation at every time. Every process that exists needs to be properly managed during a time frame that is uninterrupted of a certain measurement on a given mechanism. The optimal solution is to discover an agenda, which can be described as an distribution of the different processes to time intervals as well as machineries, which in the end has minimal length.

**Description of Job shop Scheduling Problem**

The n X m job scheduling issue can be described in the following manner. Firstly, there are n jobs and m machines. Each of the job I comprises of n1 operations. The task of production scheduling often consists of several temporal planning and this is done in the processing of several orders. The processing of an order in most instances often corresponds to the production of a certain product (Martin, 1966). This is often accomplished by the overall execution of a set of problems in what can be defined as a predefined sequence on different resources, and this is subject to several different constraints.

It is imperative to realize that the result of scheduling can be defined as a schedule which shows the temporal assignment of operations of different orders to the resources which are used. Each operation in the problem can be processed by only one machine from the candidate machine. There are several assumptions that are followed by the job scheduling problem. Firstly, each machine can be used at time zero. Secondly, each job can often be processed at time zero. Thirdly, the job scheduling problem can only process one process at a time (Pinedo, 2016). Further, there are sequences of operations for all the jobs which are pre specified. Finally, there is the assumption that all the machines are not always identical (Hooker, 2000).

A schedule can be described as a purpose that for every operation v often outlines a start time. Anagenda S can be labelled as practicable if

In the problem, the entire stretch of the schedule S is described as . It is imperative to understand that an illustration of the JSS problem can often be signified as a result of disjunctive diagram and this is represented by G=(O,A,E). In this instance, the apexes in O has over the years represented the dissimilar operations. There are diverse arcs in A which can help give precedence between the different operations (Xhafa & Abraham, 2008).

Example of a disjunctive graph

The Job shop scheduling problem is often well-thought-out to be a good depiction of the entire sphere and it has over the years received the standing of being problematic to solve (Bedoya-Valencia¸ 2007). The Job shop scheduling problem fits to the course of assessmentglitches that are NP. For example, 3*3 problem, N*2 illustration with no more than three different operations per job, the N*3 problem with more than 2 operations per job and finally the N*3 problem where all the operations that are in the sum are of unit processing time belong to the set of NP problems. There are several methods that are often used in order to try and solve the Job shop scheduling problem. The first one includes mathematical formulations and this includes mixed integer linear programming, I will examine the Multi Agent Based Job Shop and compare it with other methods.

The second method that can be used in order to get a solution to the problem is the Branch and Bound method. However, over, the years, there has been increased conflict regarding this method, where many people state that it does not actually solve the problem but rather complicate it even more (Hooker, 2000). There are many approximation methods that have been developed to try and solve the Job shop scheduling problem (Bertsimas & Gamarnik, 1998). They include the priority dispatch rules, local search methods as well as bottleneck based heuristics. Evolutionary algorithms and Ant Colony Optimization for Job Shop Scheduling Problem are also other important methods. Finally, there is also the issue of artificial intelligence and this includes constraint satisfaction approach as well as neural networks.

**Branch and Bound**

The Branch and Bound method often uses a dynamic tree structure which signifies the resolution space of different achievablearrangements (Neumann & Schneider, 1997). The search in this method often starts with the uppermost node and the entire comprehensive section is often accomplished once the lowermost node has been effectively assessed. Ever node at a level p in the entire search tree often represents anarrangement of p processes and the sequence is partial. From the unselected node the different branching operations is critical in that it regulates the set of conceivable nodes where the search can further go on and progress (Bertsimas & Gamarnik, 1998). The whole bounding procedure is critical because it helps to select the operation that continues the search and this is grounded on aprojected LB and is often attained through an extensive UB. It is of the essence to note that at any node, the projectedLB is in way superiorto the current best UB, then it is said that the selection is partial and all the subsequent descendants are consequently discarded and disregarded (Holloway, 1973).

In the priority dispatch rules, at every consecutive step all the different processes are deemed obtainable and consequently they are well scheduled and they are further allocated precedence and the process which has the uppermostimportance is then chosen in order to be sequenced. The Priority dispatch rules are often scheduled using several runs of the PDRs are they are created in this manner in order to make sure that they achieve results that are valid (Emmons & Vairaktarakis, 2013). The constraint satisfaction approach argues that there is a need to aim at plummeting the realscope of the quest space and this can be done by applying different constraints which in the end limit the directive in which several variables are designated and the arrangement in which the different conceivablestandards are allocated to every variable. There are several variables that can be examined and they include constraint propagation, variable heuristic, and value heuristic as well as backtracking (Bedoya-Valencia¸ 2007).

Multi Agent Based Job Shop Scheduling includes configurations, which are a finite set of solutions and this helps the cost function to be thoroughly optimized. Under the Multi Agent Based Job Shop method, there is also the issue of generation mechanism and this helps to generate a changeover from one different conformation to another. The neighborhood function referred to as Nx can be described as a function that defines a transition which is simple in nature from a solution x to another totally different solution and this is done by inducing a change. When choosing the selection of a neighborhood, there is a need to choose the first lower cost neighbor that is found, secondly, one should then proceed to select the best neighbor in the neighborhood and finally, there is the choosing of the best sample of the neighbors (Emmons & Vairaktarakis, 2013).

**Ant Colony Optimization for Job Shop Scheduling Problem**

Ants are social and they live in their colonies and their behavior in these colonies is often administered by the goal of colony endurance as compared to being focused on the survival of individuals. The main idea of the Ant colony optimization is often inspired by the performance of the different ants probing for their daily consumptions (Emmons & Vairaktarakis, 2013). The ants often communicate with each other regarding food sources, when the ants move, they often release different hormones on the path that they have passed. Other ants are in many cases attracted to follow them by observing the ant trail (Holloway, 1973). As compared to other different and diverse heuristics, the ACO is often characterized by distributed computation as well as positive feedback (Hooker, 2000).

In order to better understand the different operations of ants and compare them with the job shop scheduling, one should look at the operations as if they are ants. There exists a lot of similarities between the colony of ant’s foraging process and job shop scheduling. The first major similarity is that the in both, the operations must ensure that they search for a proper machine to process them (Krige, 1975). There is a need to strive in order to get the shortest path. The nest and food of the ant’s source can be said to be similar with the start and end dummy operation. In fact, if one looks at an operation such as an ant’s path for the foraging of food, then one can be able to see that indeed the relation of the two operations can be examined and interpreted as an alternative path (Chakraborty, 2009). The same case applies to the different processing times that exist in different operations of a machine and they all take different lengths of paths (Fang et al., 1995).

The ant colony algorithm often complies with the process sequence constraints. It is of the essence to note that according to the different constraints of process sequence as well as machine occupancy, ants often travel a total of nine operations of over three jobs in order to search for the operation order on every machine and from there one go ahead and gain the differential optimal or near optimal solution which is important in providing a solution for the job shop scheduling problem (Dahal et al., 2013). Therefore, given these factors, it can be said that indeed, it is feasible for one to use the Ant Colony organization to solve the job shop scheduling problem (Krige, 1975).

**Evolutionary algorithms**

The evolutionary algorithms are often inspired by different genetic algorithms. It is critical to note that the evolutionary algorithms are a recent contribution towards trying to solve the job shop scheduling problem (Chiong & Dhakal, 2009). The algorithms often use different computational models of evolutionary processes in order to solve problems related to job scheduling problem (Krige, 1975). The evolutionary approach is based on a mechanism of natural selection when it comes to biological systems. The evolutionary algorithms is further structured in a manner that is randomized in order to ensure that there is proper utilization of genetic information and this helps in the finding of a new search direction (Bedoya-Valencia¸ 2007).

**Conclusion**

The purpose of the job shop schedule is to find a schedule, which can be described as an allocation of different processes to time intermissions to machine which have the negligible length (Chiong & Dhakal, 2009). There are many methods that are used to solve the JSS, however, there is no clear or distinctive method. The Evolutionary algorithms work by the definition of anarea in the form of excellence criterion and this is then used to measure as well as associate solution contenders in a manner that can be said to be a stepwise modification of different set data constructions. If it is deemed successful, the Evolutionary algorithms often help by returning an optimal solution or in some cases, the near optimal one after a several number of different iterations. The improvement process can further be accomplished through either mutation or crossover. It is of the essence to note that indeed there evolutionary algorithms have been proposed as being important in trying to solve the issue job shop scheduling problem.

References

Bedoya-Valencia, L. (2007). *Exact and heuristic algorithms for the job shop scheduling problem with earliness and tardiness over a common due date*.

Behnke, D., & Geiger, M. J. (2012). *Test Instances for the Flexible Job Shop Scheduling Problem with Work Centers*. Hamburg: Helmut-Schmidt-Universität.

Bertsimas, D., & Gamarnik, D. (1998). *Asymptotically optimal algorithm for job shop scheduling and packet routing*. Yorktown Heights, N.Y: IBM T.J. Watson Research Center.

Blake, K. R. (1959). *Some theoretical results on the job shop scheduling problem*.

Błażewicz, J. (2007). *Handbook on scheduling: From theory to applications*. Berlin: Springer.

Błazewicz, J., Ecker, K. H., Schmidt, G., & Węglarz, J. (1994). *Scheduling in Computer and Manufacturing Systems*. Berlin, Heidelberg: Springer Berlin Heidelberg.

Buscher, U., & Shen, L. (2007). *An integer programming formulation for the lot streaming problem in a job shop environment with setups*. Dresden: Techn. Univ., Fak. Wirtschaftswiss.

Chakraborty, U. K. (2009). *Computational intelligence in flow shop and job shop scheduling*. Berlin: Springer.

Chiong, R., & Dhakal, S. (2009). *Natural Intelligence for Scheduling, Planning and Packing Problems*. Berlin, Heidelberg: Springer Berlin Heidelberg.

Dahal, K. P., Tan, K. C., & Cowling, P. I. (2007). *Evolutionary scheduling*. (Springer e-books.) Berlin: Springer.

Emmons, H., & Vairaktarakis, G. (2013). *Flow shop scheduling: Theoretical results, algorithms, and applications*. Boston, MA: Springer.

Fang, H.-L., Ross, P., Corne, D., & University of Edinburgh. (1995). *A promising hybrid GA/heuristic approach for open shop scheduling problems*. Edinburgh: University of Edinburgh, Dept. of Artificial Intelligence.

Holloway, C. A (1973). *An Interactive Program for the Job Shop Scheduling Problem with Due Dates*. Ft. Belvoir: Defense Technical Information Center.

Hooker, J. (2000). *Logic-based methods for optimization: Combining optimization and constraint satisfaction*. New York: John Wiley & Sons.

Krige, I. A. (1975). *The job shop scheduling problem: A simulation approach to finding suitable operating heuristics*.

Ku, P.-S. (1984). *Optimal scheduling policies for some stochastic flow shop, job shop, and open shop problems*.

Manne, A. S. (1960). *On the job-shop scheduling problem*. New Haven, Conn: Cowles Foundation for Research in Economics at Yale University.

Martin, P. D. (1996). *A time-oriented approach to computing optimal schedules for the job-shop scheduling problem*.

Moonen, M., & Janssens, G. K. (2004). *A Giffler-Thompson focused genetic algorithm for the static job-shop scheduling problem*. Diepenbeek: LUC, Institute for Applied Economic Research.

Morton, T. E., & Pentico, D. W. (1993). *Heuristic scheduling systems: With applications to production systems and project management*. New York: Wiley.

Neumann, K., & Schneider, W. G. (1997). *Heuristic algorithms for job shop scheduling problems with stochastic precedence constraints*. Karlsruhe: Inst. f. Wirtschaftstheorie und Operations Research, Univ. Karlsruhe.

Pinedo, M. (2016). *Scheduling: Theory, algorithms, and systems*.

Sadeh, N., & Fox, M. (1995). *Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem*. Pittsburgh, Pa: Carnegie Mellon University, the Robotics Institute.

Salais-Fierro, T. E. (2004). *Neuro-genetic approach to job shop scheduling problem*.. Sage: New York.

Schmidt, S. L. (1963). *A job shop scheduling problem*. Berkeley: University of California, May.

Sun, X. (1997). *A modified shifting bottleneck approach to job shop scheduling with sequence dependent setups (MSBSS)*.

Townsend, W. B. (1983). *Artificial intelligence techniques for industrial applications in job shop scheduling*. Monterey, Calif: Naval Postgrauduate School.

Uyar, A. S., Ozcan, E., & Urquhart, N. (2013). *Automated Scheduling and Planning: From Theory to Practice*.

Waller, L. (1972). *An improved branch-and-bound algorithm for the job-shop scheduling problem of minimising makespan*. Newcastle upon Tyne: University of Newcastle upon Tyne, Computing Laboratory.

Xhafa, F., & Abraham, A. (2008). *Metaheuristics for Scheduling in Distributed Computing Environments*.

Zoghby, J. M. (2002). *Critical arc strategies for the reentrant job shop scheduling problem with setups*.