https://optimization.cbe.cornell.edu/api.php?action=feedcontributions&user=Bjc344&feedformat=atomCornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]2023-10-02T07:46:31ZUser contributionsMediaWiki 1.35.0https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4931Job shop scheduling2021-12-07T06:33:18Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been researched and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require additional investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are in development to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum.<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are repeated until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4928Job shop scheduling2021-12-07T01:46:35Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been researched and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require additional investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are in development to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum.<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4927Job shop scheduling2021-12-07T01:36:53Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum.<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4926Job shop scheduling2021-12-07T01:36:02Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum.<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4925Job shop scheduling2021-12-07T01:35:17Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum.<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4924Job shop scheduling2021-12-07T01:33:58Z<p>Bjc344: Updated Citations</p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues<ref>Mohan, J., Lanka, K., & Rao, A. N. (2019). A Review of Dynamic Job Shop Scheduling Techniques, ''30''(Digital Manufacturing Transforming Industry Towards Sustainable Growth), 34–39. Retrieved from <nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki></ref>. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method<ref>Emmons, H., & Vairaktarakis, G. (2012). Flow Shop Scheduling: Theoretical . Springer New York Heidelberg Dordrecht London: Springer. <nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki></ref> exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956<ref>Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki></ref>. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems<ref>Coffman, E.G., Graham, R.L. Optimal scheduling for two-processor systems. ''Acta Informatica'' 1, 200–213 (1972). <nowiki>https://doi.org/10.1007/BF00288685</nowiki></ref>. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum. <br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method<ref>N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki></ref>. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method<ref>David Applegate, William Cook, (1991) A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing 3(2):149-156.<br />
<br />
<nowiki>https://doi.org/10.1287/ijoc.3.2.149</nowiki></ref>. The Branch and Bound<ref>Morshed, M.S., Meeran, S., & Jain, A.S. (2017). A State-of-the-art Review of Job-Shop Scheduling Techniques. International Journal of Applied Operational Research - An Open Access Journal, 7, 0-0. <nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki></ref> generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4923Job shop scheduling2021-12-07T00:12:07Z<p>Bjc344: /* References */</p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954 <ref>Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129. <nowiki>https://www.jstor.org/stable/3689278</nowiki></ref>. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum. 3.<br />
<br />
<br />
<br />
One common method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. This method is used for integer programing problems and is an enumerative technique. <ref>Jones, A., Rabelo, L. C., & Sharawi, A. T. (1999). Survey of job shop scheduling techniques. Wiley Encyclopedia of Electrical and Electronics Engineering. <nowiki>https://doi.org/10.1002/047134608x.w3352</nowiki></ref> An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method. The Branch and Bound generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
<br />
<nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki><br />
<br />
<br />
<nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki><br />
<br />
<br />
Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129.<br />
<br />
<nowiki>https://www.jstor.org/stable/3689278</nowiki><br />
<br />
<br />
Book:<br />
<br />
<nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki><br />
<br />
<br />
Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki><br />
<br />
<nowiki>https://pubsonline.informs.org/doi/pdf/10.1287/opre.4.2.244</nowiki><br />
<br />
<br />
Published: September 1972<br />
<br />
Optimal scheduling for two-processor systems<br />
<br />
E. G. Coffman Jr. & R. L. Graham<br />
<br />
Acta Informatica volume 1, pages200–213 (1972)Cite this article<br />
<br />
584 Accesses<br />
<br />
6 Altmetric<br />
<br />
Metrics<br />
<br />
<nowiki>https://link.springer.com/article/10.1007%2FBF00288685</nowiki><br />
<br />
<br />
N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki><br />
<br />
<br />
Branch and bound:<br />
<br />
<nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki><br />
<br />
<br />
<nowiki>https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.2.149</nowiki><br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==<br />
<references /></div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4815Job shop scheduling2021-12-06T08:44:57Z<p>Bjc344: I replaced the entire methods section based on Dr. You's much appreciated comments.</p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods ===<br />
The Job-Shop Scheduling problem has been studied and reviewed over the past 60 years, with the interest in advanced methods ever growing. This research caused a wide variety of methods to come to be. Despite this effort, many approaches require further investigation to develop them into more attractive methods for use. Due to the limitations of a single method technique when solving complex problems, techniques can be combined to create a more robust and computationally strong process. In addition to multi-method techniques, dynamic methods are being developed to help account for unforeseen production issues. There are two categories which define these dynamic methods: approximate methods and precise methods. The best results currently can be found using approaches known as meta-heuristics or iterated local search algorithms. This approach combines a meta strategy with methods used in myopic problems. With a plethora of methods, some of the more notable techniques include the Genetic Algorithms, Simulated Annealing, and Tabu Search which are all complementary as opposed to competitive.<br />
<br />
<br />
Stepping back to one of the earliest recorded works in the history of scheduling theory, there is an algorithm that focuses on efficiency. It is known as the first example of an efficient method. It is the work of David Stifler Johnson in his findings as documented in The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research article published in 1954. Johnson was an American computer scientist who specialized in optimization algorithms. The Flow Shop Method exemplifies efficiency in that it possesses a set of rules or requirement which increases polynomially with the input size to produce an optimized output. This method was designed to minimize the flow time of two machines. Johnson's work later played a significant role in subsequent Job Shop Scheduling problems due to the criterion to minimize the makespan. One of the beneficiaries of Johnson's work was Sheldon B. Akers in his article entitled A Graphical Approach to Production Scheduling Problems in 1956. In this article, he discusses his method which uses a conventional XY coordinate system to plot 2 parts of a problem with each part being an axis. By shading in the rectangle which relates to the operations on each axis and drawing a line to point P to create the program line. After analyzing the graph, one can conclude that the shortest line corresponds to the program which completes both parts in the least amount of time.<br />
<br />
<br />
Despite the high number of potential variables involved in the Job-Shop Problem, one of the more commonly known methods which strived for efficiency was used in solving uniform length jobs with 2 processor systems. This competitive method published in 1972 is called the Coffman-Graham algorithm, and is explained in their article Optimal scheduling for two-processor systems. Named after Edward G. Coffman, Jr. and Ronald Graham, the problem makes a sequence of levels by organizing each element of a partially ordered set. This algorithm assigns a latter element a lower sequence or level, which ensures that each individual level has a distinct and fixed bound width. When that width is equal to 2, the number of levels is at a minimum. 3.<br />
<br />
<br />
One general method is a technique that can be applied to other MILP problems outside of the Job-Shop Scheduling problem, called the Branch and Bound method. The Branch and Bound method can be used to solve simpler problems such as those with only one machine. An example of this is detailed below. For more complicated problems, a dynamic solution is required, one of which combines the Branch and Bound method with the Cutting-Plane method. The Branch and Bound generally presents a problem tree in which the branches are traversed using the lower bound calculated to find the optimal solution. The problem is recursively divided into sub-problems as necessary. Prior to enumerating, the feasible solutions are compared to find the smallest bound. The lowest feasible solution is then bounded upon, adding the constraint to restrict the set of possible solutions. These steps are bounded upon until the final result has yielded the optimized solution. <br />
<br />
<br />
<nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki><br />
<br />
<br />
<nowiki>https://www.sciencedirect.com/science/article/pii/S2351978919300368</nowiki><br />
<br />
<br />
Garey, M. R., Johnson, D. S. and Sethi, R. (1976) The Complexity of Flow Shop and Job-Shop Scheduling, Mathematics of Operations Research, May, 1(2), 117-129.<br />
<br />
<nowiki>https://www.jstor.org/stable/3689278</nowiki><br />
<br />
<br />
Book:<br />
<br />
<nowiki>https://books.google.com/books?hl=en&lr=&id=4UWMlwrescgC&oi=fnd&pg=PR3&dq=flow+shop+scheduling&ots=xz5Rkg6ATJ&sig=qSGDuAAjEmvhJosC9qng_1pZIA8#v=onepage&q=flow%20shop%20scheduling&f=false</nowiki><br />
<br />
<br />
Sheldon B. Akers, Jr., (1956) Letter to the Editor—A Graphical Approach to Production Scheduling Problems. Operations Research 4(2):244-245. <nowiki>https://doi.org/10.1287/opre.4.2.244</nowiki><br />
<br />
<nowiki>https://pubsonline.informs.org/doi/pdf/10.1287/opre.4.2.244</nowiki><br />
<br />
<br />
Published: September 1972<br />
<br />
Optimal scheduling for two-processor systems<br />
<br />
E. G. Coffman Jr. & R. L. Graham<br />
<br />
Acta Informatica volume 1, pages200–213 (1972)Cite this article<br />
<br />
584 Accesses<br />
<br />
6 Altmetric<br />
<br />
Metrics<br />
<br />
<nowiki>https://link.springer.com/article/10.1007%2FBF00288685</nowiki><br />
<br />
<br />
N. Agin, Optimum seeking with branch and bound. Management Science, 13, 176-185, 1966.<br />
<br />
<nowiki>https://www.semanticscholar.org/paper/Optimum-Seeking-with-Branch-and-Bound-Agin/8d999d24c43d42685726a5658e3c279530e5b88f</nowiki><br />
<br />
<br />
Branch and bound:<br />
<br />
<nowiki>https://neuro.bstu.by/ai/To-dom/My_research/Papers-0/For-courses/Job-SSP/jain.pdf</nowiki><br />
<br />
<br />
<nowiki>https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.2.149</nowiki><br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4574Job shop scheduling2021-11-29T04:57:24Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that ''X<sub>ij</sub>'' is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, ''X<sub>ij</sub>'' is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
''X<sub>ij</sub>'' = 1<br />
<br />
''X<sub>ij</sub>'' = 0<br />
<br />
''i'' = 1, 2, 3<br />
<br />
''J'' = ''A'', ''B'', ''C''<br />
<br />
''T'' = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub>''<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where ''i'' = 3, suppose ''X<sub>3a</sub>'' = 1 by placing ''A'' in the third position, then suppose ''X<sub>3b</sub>'' = 1 by placing ''B'' in the third position, and lastly suppose ''X<sub>3c</sub>'' = 1 by placing ''C'' in the third position.<br />
<br />
Starting with ''X<sub>3a</sub>'' = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to ''d<sub>3</sub>''. This same process can be used to calculate ''d<sub>3</sub>'' for both of the other branch (''X<sub>3b</sub>'' = 1 and ''X<sub>3c</sub>'' = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set ''X<sub>2a</sub>'' = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get ''d<sub>2</sub>''. The total delay must then be greater than or equal to ''d<sub>2</sub>'' plus ''d<sub>3</sub>''. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when ''i'' = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when ''i'' = 3 and when ''i'' = 2. To calculate ''d<sub>1</sub>'', take the due date of the job when ''i'' = 1 and subtract the completion time of the that job. Then sum ''d<sub>1</sub>'', ''d<sub>2</sub>'', and ''d<sub>3</sub>'' to calculate the total delay, ''T''.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest ''T'' shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2" /> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always be completed on day 15. With this information, we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example, that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4570Job shop scheduling2021-11-29T04:49:14Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref name=":2">https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that ''X<sub>ij</sub>'' is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, ''X<sub>ij</sub>'' is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
''X<sub>ij</sub>'' = 1<br />
<br />
''X<sub>ij</sub>'' = 0<br />
<br />
''i'' = 1, 2, 3<br />
<br />
''J'' = ''A'', ''B'', ''C''<br />
<br />
''T'' = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub>''<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where ''i'' = 3, suppose ''X<sub>3a</sub>'' = 1 by placing ''A'' in the third position, then suppose ''X<sub>3b</sub>'' = 1 by placing ''B'' in the third position, and lastly suppose ''X<sub>3c</sub>'' = 1 by placing ''C'' in the third position.<br />
<br />
Starting with ''X<sub>3a</sub>'' = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to ''d<sub>3</sub>''. This same process can be used to calculate ''d<sub>3</sub>'' for both of the other branch (''X<sub>3b</sub>'' = 1 and ''X<sub>3c</sub>'' = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set ''X<sub>2a</sub>'' = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get ''d<sub>2</sub>''. The total delay must then be greater than or equal to ''d<sub>2</sub>'' plus ''d<sub>3</sub>''. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when ''i'' = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when ''i'' = 3 and when ''i'' = 2. To calculate ''d<sub>1</sub>'', take the due date of the job when ''i'' = 1 and subtract the completion time of the that job. Then sum ''d<sub>1</sub>'', ''d<sub>2</sub>'', and ''d<sub>3</sub>'' to calculate the total delay, ''T''.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest ''T'' shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==Job-Shop Scheduling - CNC Machine Numerical Example==<br />
<br />
This example demonstrates how a Job-Shop Scheduling problem can be solved using the Branch and Bound method explained above. <ref name=":2" /> <br />
<br />
There are three mechanical parts that need to be processed (jobs) on a single available CNC machine. Each job has a finite duration to complete and a due date in the overall project schedule. This information is shown in the following table:<br />
{| class="wikitable"<br />
|+CNC Part Processing Information<br />
!Job<br />
!Duration (days)<br />
!Due Date<br />
|-<br />
|A<br />
|6<br />
|Day 8<br />
|-<br />
|B<br />
|4<br />
|Day 4<br />
|-<br />
|C<br />
|5<br />
|Day 12<br />
|}<br />
The goal of this problem is to determine which sequence the jobs should be completed in to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABC.<br />
[[File:CompOp Wiki.png|thumb|799x799px|'''Branch and Bound Flow Diagram:''' method used to solve a simple job-shop scheduling problem coordinating 3 jobs requiring shared use of 1 machine to complete. Each job has a different deadline, and the goal is to minimize total delay in the project.]]<br />
{| class="wikitable"<br />
|+Delay for Sequence (A, B, C)<br />
!Job<br />
!Completion Day<br />
!Delay<br />
|-<br />
|A<br />
|6<br />
|''d<sub>1</sub>'' = 6-8 = -2 -> 0<br />
|-<br />
|A, B<br />
|6+4 = 10<br />
|''d<sub>2</sub> = 10- 4 = 6''<br />
|-<br />
|A, B, C<br />
|6+4+5<br />
|''d<sub>3</sub> = 15 - 12 = 3''<br />
|}<br />
By beginning with job A at day 0, it will be completed by day 6. This is 2 days before the job A deadline and adds no delay to our overall schedule. At completion of job B we add the 6 days used on job A to the 4 needed for job B to get a completion time of 10 days. This yields a 6 day delay, as the deadline for job B was day 4. Finally we repeat that process for job C and see an additional 3 day delay. The total project delay T is equal to the summation of the accrued delay for each task: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> = 0 + 6 + 3 = 9 days.''<br />
<br />
Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all feasible solutions. We first define our decision variables where ''X<sub>ij</sub>'' = 1 if job j is put in the ith position, and ''X<sub>ij</sub>'' = 0 otherwise. Positions of jobs in the sequence are denoted by i = 1, 2, 3; Jobs are denoted by j = A, B, C. <br />
<br />
The following explanation can be visualized in the Branch and Bound flow diagram. Regardless of the sequence, we know that the last job will always complete at day 15. With this information we can calculate which job will result in the smallest possible delay if put third in the sequence. For our example that is task C, showing that the smallest the delay can be is 3 days. From there we branch again at the node with the smallest possible delay and repeat the process for determining the best choice for the second job in the sequence. Here we see that Job A in the second position yields a delay of at least 5. Finally, with only one option available for the job in the first position, we have reached our optimal sequence: BAC. This sequence minimized delay to 5 days, and thus is the optimal solution. <br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. However, there are many distinctions that can be made between every utilization of the JSSP so there is continuous research ongoing to improve adaptability of the problem. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=File:Image45.png&diff=4530File:Image45.png2021-11-29T03:34:02Z<p>Bjc344: </p>
<hr />
<div>Image455</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4411Job shop scheduling2021-11-29T00:50:59Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref>https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that Xij is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, ''X<sub>ij</sub>'' is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
''X<sub>ij</sub>'' = 1<br />
<br />
''X<sub>ij</sub>'' = 0<br />
<br />
''i'' = 1, 2, 3<br />
<br />
''J'' = ''A'', ''B'', ''C''<br />
<br />
''T'' = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub>''<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where ''i'' = 3, suppose ''X<sub>3a</sub>'' = 1 by placing ''A'' in the third position, then suppose ''X<sub>3b</sub>'' = 1 by placing ''B'' in the third position, and lastly suppose ''X<sub>3c</sub>'' = 1 by placing ''C'' in the third position.<br />
<br />
Starting with ''X<sub>3a</sub>'' = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to ''d<sub>3</sub>''. This same process can be used to calculate ''d<sub>3</sub>'' for both of the other branch (''X<sub>3b</sub>'' = 1 and ''X<sub>3c</sub>'' = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set ''X<sub>2a</sub>'' = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get ''d<sub>2</sub>''. The total delay must then be greater than or equal to ''d<sub>2</sub>'' plus ''d<sub>3</sub>''. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when ''i'' = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when ''i'' = 3 and when ''i'' = 2. To calculate ''d<sub>1</sub>'', take the due date of the job when ''i'' = 1 and subtract the completion time of the that job. Then sum ''d<sub>1</sub>'', ''d<sub>2</sub>'', and ''d<sub>3</sub>'' to calculate the total delay, ''T''.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest ''T'' shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==At least one numerical example==<br />
<br />
encouraged to have more than one<br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
....improve the adaptability?<br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4402Job shop scheduling2021-11-29T00:38:42Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref>https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that Xij is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, ''X<sub>ij</sub>'' is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
''X<sub>ij</sub>'' = 1<br />
<br />
''X<sub>ij</sub>'' = 0<br />
<br />
''i'' = 1, 2, 3<br />
<br />
''J'' = ''A'', ''B'', ''C''<br />
<br />
''T'' = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub>''<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where ''i'' = 3, suppose ''X<sub>3a</sub>'' = 1 by placing ''A'' in the third position, then suppose ''X<sub>3b</sub>'' = 1 by placing ''B'' in the third position, and lastly suppose ''X<sub>3c</sub>'' = 1 by placing ''C'' in the third position.<br />
<br />
Starting with ''X<sub>3a</sub>'' = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to ''d<sub>3</sub>''. This same process can be used to calculate ''d<sub>3</sub>'' for both of the other branch (''X<sub>3b</sub>'' = 1 and ''X<sub>3c</sub>'' = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set ''X<sub>2a</sub>'' = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get ''d<sub>2</sub>''. The total delay must then be greater than or equal to ''d<sub>2</sub>'' plus ''d<sub>3</sub>''. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when I = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when I = 3 and when I = 2. To calculate ''d<sub>1</sub>'', take the due date of the job when I = 1 and subtract the completion time of the that job. Then sum ''d<sub>1</sub>'', ''d<sub>2</sub>'', and ''d<sub>3</sub>'' to calculate the total delay, ''T''.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest ''T'' shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==At least one numerical example==<br />
<br />
encouraged to have more than one<br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
....improve the adaptability?<br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4395Job shop scheduling2021-11-29T00:33:54Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref>https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that Xij is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, X_{ij} is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
''X<sub>ij</sub>'' = 1<br />
<br />
''X<sub>ij</sub>'' = 0<br />
<br />
''i'' = 1, 2, 3<br />
<br />
''J'' = A, B, C<br />
<br />
''T'' = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub>''<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where ''i'' = 3, suppose ''X<sub>3a</sub>'' = 1 by placing A in the third position, then suppose ''X<sub>3b</sub>'' = 1 by placing B in the third position, and lastly suppose ''X<sub>3c</sub>'' = 1 by placing C in the third position.<br />
<br />
Starting with ''X<sub>3a</sub>'' = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to ''d<sub>3</sub>''. This same process can be used to calculate ''d<sub>3</sub>'' for both of the other branch (''X<sub>3b</sub>'' = 1 and ''X<sub>3c</sub>'' = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set ''X<sub>2a</sub>'' = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get ''d<sub>2</sub>''. The total delay must then be greater than or equal to ''d<sub>2</sub>'' plus ''d<sub>3</sub>''. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when I = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when I = 3 and when I = 2. To calculate ''d<sub>1</sub>'', take the due date of the job when I = 1 and subtract the completion time of the that job. Then sum ''d<sub>1</sub>'', ''d<sub>2</sub>'', and ''d<sub>3</sub>'' to calculate the total delay, ''T''.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest ''T'' shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==At least one numerical example==<br />
<br />
encouraged to have more than one<br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
....improve the adaptability?<br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4385Job shop scheduling2021-11-29T00:16:19Z<p>Bjc344: </p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref>https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that Xij is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, X_{ij} is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
Xij = 1<br />
<br />
Xij = 0<br />
<br />
i = 1, 2, 3<br />
<br />
J = A, B, C<br />
<br />
T = d1 + d2 +d3<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where I = 3, suppose X3a = 1 by placing A in the third position, then suppose X3b = 1 by placing B in the third position, and lastly suppose X3c = 1 by placing C in the third position.<br />
<br />
Starting with X3a = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to d3. This same process can be used to calculate d3 for both of the other branch (X3b = 1 and X3c = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set X2a = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get d2. The total delay must then be greater than or equal to d2 plus d3. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when I = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when I = 3 and when I = 2. To calculate d1, take the due date of the job when I = 1 and subtract the completion time of the that job. Then sum d1, d2, and d3 to calculate the total delay, T.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest T shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==At least one numerical example==<br />
<br />
encouraged to have more than one<br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
....improve the adaptability?<br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344https://optimization.cbe.cornell.edu/index.php?title=Job_shop_scheduling&diff=4380Job shop scheduling2021-11-29T00:13:03Z<p>Bjc344: /* Theory/Methodology/Algorithms */</p>
<hr />
<div><br />
Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)<br />
<br />
==Introduction==<br />
The Job-Shop Scheduling Problem (JSSP) is a combinatorial optimization problem, which mainly concerns the operations industry. The aim of the problem is to optimize the schedule for allocation of shared resources over time to competing activities<ref name=":0">T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.</ref>. <br />
<br />
Within a JSSP you will have ''n'' number of jobs (''J''<sub>1</sub>, ''J''<sub>2</sub>, ..., ''J<sub>n</sub>'' ), that will need to be completed using a ''m'' number shared resources, most commonly denoted as machines (''M''<sub>1</sub>, ''M''<sub>2</sub>, ..., ''M<sub>m</sub>'' ). Each job will have operations (''O'') that will need to be completed in a specific order in order for the job to be completed. Operations must be completed at specific machines and require a specific amount of processing time (''p'') on that machine.Machines are assumed to only be able to process one operation at a time, driving the need to optimize the order in which these operations are completed.<ref name=":0" /><ref>P. Brucker, B. Jurisch and B. Sievers. "A branch and bound algorithm for the job-shop scheduling problem", Discrete Applied Mathematics, 1994.</ref> The goal of the JSSP is to minimize the overall time it takes to complete all ''n j''obs within the problem.<br />
<br />
==Theory/Methodology/Algorithms==<br />
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]<br />
The job shop scheduling problem is NP-hard meaning it’s complexity class for non-deterministic polynomial-time is least as hard as the hardest of problems in NP. As an input, there is a finite set ''J'' of jobs and a finite set of ''M'' of machines. Some jobs may need to be processed through multiple machines giving us an optimal potential processing order for each job. The processing time of the job ''j'' on machine ''m'' can be defined as the nonnegative integer . In order to minimize total completion time, the job shop can find the optimal schedule of ''J'' on ''M''<ref>D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.</ref>.<br />
<br />
The assumptions made for solving the problem are as follows. The number of operations for each job is finite. The processing time for each operation in a particular machine is defined. There is a pre-defined sequence of operations that has to be maintained to complete each job. Delivery times of the products are undefined. No setup cost and tardiness cost. A machine can process only one job at a time. Each job visits each machine only once. No machine can deal with more than one type of task. The system cannot be interrupted until each operation of each job is finished. No machine can halt a job and start another job, before finishing the previous one<ref>K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.</ref>. Given these assumptions, the problem can be solved at complexity class NP-hard. <br />
<br />
One way of visualizing the job shop scheduling problem is using a Gantt-Chart. Given a problem of size 3 x 3 (''J'' x ''M''), a solution can be represented as shown in Figure 1. Depending on the job, the operating time on each machine could vary. <br />
<br />
=== Methods: Branch and Bound ===<br />
One of the most common problem solving methods for the Job Shop Scheduling Problem is the Branch and Bound method. <ref>https://www.youtube.com/watch?v=UGvc-qujB-o&ab_channel=YongWang</ref> The first step is to define the decision variables, specifying that Xij is equal to 1 given that job j is placed in the ith position. Outside of that stipulation, Xij is equal to 0. The jobs are referred to as A, B, and C. The total delay, T, is equal to delay 1 plus delay 2 plus delay 3.The durations and due dates must be specified to produce a solvable problem. Each branch or option will be explored to find the most minimized delay time and thus the most optimized job sequence. Thus we have:<br />
<br />
Xij = 1<br />
<br />
Xij = 0<br />
<br />
I = 1, 2, 3<br />
<br />
J = A, B, C<br />
<br />
T = d1 + d2 +d3<br />
<br />
Initially, the delay times, the total delay, or the position of any of the jobs are all unknown. The Branch and Bound method sets out to solve for each of those to arrive at the optimal sequence for which the jobs need to be performed to minimize the total delay time assuming the completion of all the jobs.<br />
<br />
Starting with the last position, where I = 3, suppose X3a = 1 by placing A in the third position, then suppose X3b = 1 by placing B in the third position, and lastly suppose X3c = 1 by placing C in the third position.<br />
<br />
Starting with X3a = 1, no matter what the first 2 positions sum to, it is known that the third position will always be completed on the final day, which is computed by adding all the durations together. Next the delay is calculated by subtracting the due date of job A from the total duration; this is delay 3. This states then that the total delay time is less than or equal to d3. This same process can be used to calculate d3 for both of the other branch (X3b = 1 and X3c = 1).<br />
<br />
Next, take the case which provided the smallest total delay value since this is the most likely to provide the shortest delay time. Assuming this case, the third position is decided. This does not guarantee the shortest position, however, so the other methods may need to be calculated as well. This branch is extended by checking the second position. Position 2 could now be one of the remaining two positions, let's assume option A and B remain. Set X2a = 1 and X2b =1 respectively for each branch. For X2a = 1, take the total duration and subtract the duration of the selected job for I = 3, (C in this case) from the total. Subtract the due date of job A from that calculated value to get d2. The total delay must then be greater than or equal to d2 plus d3. Repeat this process for X2b = 1.<br />
<br />
The branch with the smaller total delay time is likely the minimized solution, but this option needs to be checked by placing the remaining job in the first position. To do this, calculate the completion time of the job when I = 1 by taking the total duration of the jobs summed and subtracting the duration of the job when I = 3 and when I = 2. To calculate d1, take the due date of the job when I = 1 and subtract the completion time of the that job. Then sum d1, d2, and d3 to calculate the total delay, T.<br />
<br />
Lastly, ensure each total delay time is not less than previously found. If one of the other branches has a value that is less than or equal to the calculated T, follow this same process to check the other 2 initial branches. The smallest T shows the optimal solution and the sequence utilized to provide the minimized delay time.<br />
<br />
[https://www.youtube.com/watch?v=UGvc-qujB-o Operations Research 09D: Job Shop Scheduling Problem]<br />
<br />
==At least one numerical example==<br />
<br />
encouraged to have more than one<br />
<br />
==Applications==<br />
There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem at hand, for a variety of applications. <br />
<br />
The most obvious example can be found in the manufacturing industry, as the name suggests. It is common for some production jobs to require certain machines to perform tasks, due to the proper capabilities or equipment of a given machine. This adds an additional layer of complexity to the problem, because not any job can be processed on any machine. This is known as flexible manufacturing. Furthermore, there are many uncertain factors that are not accounted for in the basic understanding of the problem, such as delays in delivery of necessary supplies, significant absence of workers, equipment malfunction, etc. <ref>Jianzhong Xu, Song Zhang, Yuzhen Hu, "Research on Construction and Application for the Model of Multistage Job Shop Scheduling Problem", ''Mathematical Problems in Engineering'', vol. 2020, Article ID 6357394, 12 pages, 2020. <nowiki>https://doi.org/10.1155/2020/6357394</nowiki></ref><br />
<br />
....improve the adaptability?<br />
<br />
This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that computer instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions can be thought of as the "jobs" to be performed and the processors required for each task can be compared to the "machines". Here we would want to schedule the order of instructions such that the number of operations performed is maximized to make the computer as efficient as possible.<ref>Peter Brucker, "The Job-Shop Problem: Old and New Challenges", ''Universit¨at Osnabr¨uck, Albrechtstr.'' 28a, 49069 Osnabr¨uck, Germany, pbrucker@uni-osnabrueck.de</ref> Within this application, there are a further variety of heuristic methods considered as to how to execute tasks to maximize efficiency and minimize costs, including minimum completion time, duplex, max-min, min-min, tabu search, and genetic algorithm. Each of these methods have their advantages and disadvantages, weighing the importance of minimizing execution time versus finding the closest to optimal solution.<ref>Abdeyazdan M., Rahmani A.M. (2008) Multiprocessor Task Scheduling using a new Prioritizing Genetic Algorithm based on number of Task Children. In: Kacsuk P., Lovas R., Németh Z. (eds) Distributed and Parallel Systems. Springer, Boston, MA. <nowiki>https://doi.org/10.1007/978-0-387-79448-8_10</nowiki></ref><br />
[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png|thumb|Fig 2. Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]<br />
<br />
<br />
With the progression of automation in recent years, robotic tasks such as moving objects from one location to another are similarly optimized. In this application, the extent of movement of the robot is minimized while conducting the most amount of transport jobs to support the most effective productivity of the robot. There are additional nuances within this problem as well, such as the rotational movement capabilities of the robot, the layout of the robots within the system, and the number of parts or units the robot is able to produce. While each of these factors contribute to the complexity of the job shop scheduling problem, they are all worth considering as more and more companies are proceeding in this direction to reduce labor costs and increase flexibility and safety of the enterprise.<ref name=":1">M.Selim Akturk, Hakan Gultekin, Oya Ekin Karasan, Robotic cell scheduling with operational flexibility, Discrete Applied Mathematics, Volume 145, Issue 3, 2005, Pages 334-348, ISSN 0166-218X</ref> <br />
<br />
<br />
==Conclusions==<br />
Job-Shop Scheduling Problems are NP-hard combinatorial optimization problems, predominately used for operations applications. JSSPs minimize the overall time a set of jobs takes to complete, by optimizing the schedule in which shared resources are set to be allocated.<br />
<br />
JSSPs can be solved using a variety of methods and algorithms.<br />
<br />
There are multiple applications for JSSPs, the predominate application is within the manufacturing industry as the name implies. Other applications for this problem could also be the optimization of a computer's processing power as it executes multiple programs, optimization of automated equipment or robots, as well as a number of other applications.<br />
<br />
==References==</div>Bjc344