Job shop scheduling - Revision history

Carlycozzolino: /* Applications */

2021-12-15T20:46:30Z

Applications

← Older revision		Revision as of 16:46, 15 December 2021
Line 111:		Line 111:

	==Applications==		==Applications==
	There are several ways in which the job-shop scheduling problem can be adapted, 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. Job-shop scheduling helps organizations to save valuable time and money		[[File:An-example-of-the-job-shop-scheduling-problem-with-three-components-jobs.png\|thumb\|'''Figure 6''': A manufacturing example of job-shop scheduling.<ref>Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem - Scientific Figure on ResearchGate. Available from: <nowiki>https://www.researchgate.net/figure/An-example-of-the-job-shop-scheduling-problem-with-three-components-jobs_fig7_314563199</nowiki> [accessed 15 Dec, 2021]</ref>]]
			There are several ways in which the job-shop scheduling problem can be adapted, 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. Job-shop scheduling helps organizations to save valuable time and money.

	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 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>		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 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>

	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>		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>
	[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png\|thumb\|'''Figure 6''': Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]

	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>


			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>
	==Conclusions==		==Conclusions==
	JSSPs are used to optimize the allocation of shared resources in order to reduce the time and cost needed in order to complete a set amount of tasks. JSSPs account for the number of resources available, the operations needed to complete a job or task, the required order of operations, the necessary resources needed for each operation, as well as the necessary time needed with a resource for each operation in order to create an optimal schedule to complete all jobs. While this problem is used predominately for machining purposes, as the name implies, it can be adapted to be used on a variety of other cases within and outside of manufacturing. Other applications for this problem include the optimization of a computer's processing power as it executes multiple programs and optimization of automated equipment or robots.		JSSPs are used to optimize the allocation of shared resources in order to reduce the time and cost needed in order to complete a set amount of tasks. JSSPs account for the number of resources available, the operations needed to complete a job or task, the required order of operations, the necessary resources needed for each operation, as well as the necessary time needed with a resource for each operation in order to create an optimal schedule to complete all jobs. While this problem is used predominately for machining purposes, as the name implies, it can be adapted to be used on a variety of other cases within and outside of manufacturing. Other applications for this problem include the optimization of a computer's processing power as it executes multiple programs and optimization of automated equipment or robots.

Ms3693 at 02:29, 15 December 2021

2021-12-15T02:29:07Z

← Older revision		Revision as of 22:29, 14 December 2021
Line 102:		Line 102:
	[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any job, delay for any job, and total project delay are all unknown.]]		[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any job, delay for any job, and total project delay are all unknown.]]
	We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all job durations that need to be completed. In this example we know the final task will complete on day 24, as seen in table 2 above. Next we can calculate the delay that the final task will have, given it is the last job in the sequence, by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the second to last job in the sequence. Job A is due on day 5: 24 - 5 = 19 delay. Job B is due on day 6: 24 - 6 = 18 delay. Job C is due on day 16: 24 - 16 = 8 delay. Job D is due on day 14: 24 - 14 = 10 delay.		We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all job durations that need to be completed. In this example we know the final task will complete on day 24, as seen in table 2 above. Next we can calculate the delay that the final task will have, given it is the last job in the sequence, by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the second to last job in the sequence. Job A is due on day 5: 24 - 5 = 19 delay. Job B is due on day 6: 24 - 6 = 18 delay. Job C is due on day 16: 24 - 16 = 8 delay. Job D is due on day 14: 24 - 14 = 10 delay.
	[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible project delay given each job is placed last in the sequence.]]		[[File:Example2 2.png\|none\|thumb\|433x433px\|'''Figure 3:''' Example Step 2 - Determine the smallest possible project delay given each job is placed last in the sequence.]]

	Figure 3 shows that job C in the final position of the sequence yields the smallest possible project delay T >= 8. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the known due dates of each task to determine the path with the smallest accrued delay. Job A is due on day 5: 15 - 5 = 10 delay. Job B is due on day 6: 15 - 6 = 9 delay. Job D is due on day 14: 15 - 14 = 1 delay.		Figure 3 shows that job C in the final position of the sequence yields the smallest possible project delay T >= 8. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the known due dates of each task to determine the path with the smallest accrued delay. Job A is due on day 5: 15 - 5 = 10 delay. Job B is due on day 6: 15 - 6 = 9 delay. Job D is due on day 14: 15 - 14 = 1 delay.
Line 116:		Line 116:

	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>		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>
	[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png\|thumb\|'''Figure 3''': Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]		[[File:Screen Shot 2021-11-28 at 6.00.24 PM.png\|thumb\|'''Figure 6''': Comparison of Gantt charts for the standard and operational assignment cases, two common methods of robot move cycles.<ref name=":1" />]]

	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>		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>

Ms3693 at 02:27, 15 December 2021

2021-12-15T02:27:11Z

← Older revision		Revision as of 22:27, 14 December 2021
Line 51:		Line 51:
	There are four jobs that need to be processed on a single shared resource. 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:		There are four jobs that need to be processed on a single shared resource. 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:
	{\| class="wikitable"		{\| class="wikitable"
	\|+Job Information		\|+Table 1: Job Information
	!Job		!Job
	!Duration (days)		!Duration (days)
Line 72:		Line 72:
	\|Day 14		\|Day 14
	\|}		\|}
	The goal of this method is to determine the order in which the jobs should be processed on the shared resource to minimize total accrued project delay. There are n! feasible solutions for a job shop scheduling problem, therefore there are 4! = 24 feasible solutions for this example. The completion day is the summation of all job durations in a given sequence. The delay per job is found by subtracting a job's due date by the job's calculated completion day. Total project delay is the summation of all individual job delays. The following table shows an example to calculate delay for one particular sequence, ABCD.		The goal of this method is to determine the order in which the jobs should be processed on the shared resource to minimize total accrued project delay. There are n! feasible solutions for a job shop scheduling problem, therefore there are 4! = 24 feasible solutions for this example. The project completion day is the summation of all job durations in a given sequence. The delay per job is found by subtracting a job's due date by the job's calculated completion day. Total project delay is the summation of all individual job delays. The following table shows an example to calculate delay for one particular sequence, ABCD.
	{\| class="wikitable"		{\| class="wikitable"
	\|+Delay for Sequence (A, B, C, D)		\|+Table 2: Delay for Sequence (A, B, C, D)
	!Job		!Job
	!Completion Day		!Completion Day
Line 95:		Line 95:
	\|''d<sub>4</sub> = 24 - 14 = 10''		\|''d<sub>4</sub> = 24 - 14 = 10''
	\|}		\|}
	By beginning with job A at day 0, it will be completed by day 3. This is 2 days before the job A deadline and adds no delay to the overall schedule. At completion of job B we add the 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. The total project delay T is equal to the summation of the accrued delay for each ~~jop~~: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''		By beginning with job A at day 0, it will be completed by day 3. This is 2 days before the job A deadline and adds no delay to the overall schedule. At completion of job B we add the 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. The total project delay T is equal to the summation of the accrued delay for each job: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''

	Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all 24 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, 4; Jobs are denoted by j = A, B, C, D.		Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all 24 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, 4; Jobs are denoted by j = A, B, C, D.

	Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown.		Initially, the ideal sequence of the jobs, the delay for any individual job, or the total project delay are unknown.
	[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any job, delay for any job, and total delay are all unknown.]]		[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any job, delay for any job, and total project delay are all unknown.]]
	We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all ~~jobs~~ that need to be completed. In this example we know the final task will complete on day 24. Next we can calculate the delay that the final task will have, given it is the last job in the sequence, by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the second to last job in the sequence.		We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all job durations that need to be completed. In this example we know the final task will complete on day 24, as seen in table 2 above. Next we can calculate the delay that the final task will have, given it is the last job in the sequence, by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the second to last job in the sequence. Job A is due on day 5: 24 - 5 = 19 delay. Job B is due on day 6: 24 - 6 = 18 delay. Job C is due on day 16: 24 - 16 = 8 delay. Job D is due on day 14: 24 - 14 = 10 delay.
	[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible project delay given each job is placed last in the sequence.]]		[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible project delay given each job is placed last in the sequence.]]

	Figure 3 shows that job C in the final position of the sequence yields the smallest possible project delay T. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the known due dates of each task to determine the path with the smallest accrued delay. Job A is due on day 5: 15 - 5 = 10 delay. Job B is due on day 6: 15 - 6 = 9 delay. Job D is due on day 14: 15 - 14 = 1 delay.		Figure 3 shows that job C in the final position of the sequence yields the smallest possible project delay T >= 8. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the known due dates of each task to determine the path with the smallest accrued delay. Job A is due on day 5: 15 - 5 = 10 delay. Job B is due on day 6: 15 - 6 = 9 delay. Job D is due on day 14: 15 - 14 = 1 delay.
	[[File:Example3.png\|none\|thumb\|785x785px\|'''Figure 4:''' Example Step 3 - Branch from node C and determine which job will yeild the lowest possible delay if run second to last. It is known that this job will complete on day 15 (Time to complete job C subtracted by total time to complete jobs 24-9=15).]]		[[File:Example3.png\|none\|thumb\|785x785px\|'''Figure 4:''' Example Step 3 - Branch from node C and determine which job will yeild the lowest possible delay if run second to last. It is known that this job will complete on day 15 (Time to complete job C subtracted by total time to complete jobs 24-9=15).]]

Ms3693 at 02:17, 15 December 2021

2021-12-15T02:17:23Z

← Older revision		Revision as of 22:17, 14 December 2021
Line 100:		Line 100:

	Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown.		Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown.
	[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any ~~task~~, delay for any ~~task~~, and total delay are all unknown.]]		[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any job, delay for any job, and total delay are all unknown.]]
	We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all jobs that need to be completed. In this example we know the final task will complete on day 24. Next we can calculate the delay that the final task will have given it is the last job in the sequence by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the ~~next~~ to last job in the sequence.		We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all jobs that need to be completed. In this example we know the final task will complete on day 24. Next we can calculate the delay that the final task will have, given it is the last job in the sequence, by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the second to last job in the sequence.
	[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible delay given each ~~possible task~~ is placed last in the sequence.]]		[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible project delay given each job is placed last in the sequence.]]

	Figure 3 shows that job C ~~has~~ in the final position of the sequence yields the smallest possible delay. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the due dates of each task to determine the path with the smallest accrued delay.		Figure 3 shows that job C in the final position of the sequence yields the smallest possible project delay T. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the known due dates of each task to determine the path with the smallest accrued delay. Job A is due on day 5: 15 - 5 = 10 delay. Job B is due on day 6: 15 - 6 = 9 delay. Job D is due on day 14: 15 - 14 = 1 delay.
	[[File:Example3.png\|none\|thumb\|785x785px\|'''Figure 4:''' Example Step 3 - Branch from node C and determine which job will yeild the lowest possible delay if run second to last. It is known that this job will complete on day 15 (Time to complete job C subtracted by total time to complete jobs 24-9=15).]]		[[File:Example3.png\|none\|thumb\|785x785px\|'''Figure 4:''' Example Step 3 - Branch from node C and determine which job will yeild the lowest possible delay if run second to last. It is known that this job will complete on day 15 (Time to complete job C subtracted by total time to complete jobs 24-9=15).]]

	By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.		By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay. Figure 5 shows the completed Branch and Bound diagram, showing how an optimal solution of sequence: ABDC and a total project delay of T = 11 days can be achieved.
	[[File:Example4.png\|none\|thumb\|1153x1153px\|Figure 5: Example Step 4/5]]		[[File:Example4.png\|none\|thumb\|1153x1153px\|'''Figure 5:''' Example Step 4/5 - Branch and Bound Flow Diagram: method used to solve a simple job-shop scheduling problem coordinating 4 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. Optimal solution found to be sequence ABDC with a total project delay of T = 11 days.]]

	==Applications==		==Applications==

Ms3693 at 02:07, 15 December 2021

2021-12-15T02:07:23Z

← Older revision		Revision as of 22:07, 14 December 2021
Line 108:		Line 108:

	By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.		By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.
			[[File:Example4.png\|none\|thumb\|1153x1153px\|Figure 5: Example Step 4/5]]

	==Applications==		==Applications==

Ms3693 at 02:05, 15 December 2021

2021-12-15T02:05:27Z

← Older revision		Revision as of 22:05, 14 December 2021
Line 99:		Line 99:
	Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all 24 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, 4; Jobs are denoted by j = A, B, C, D.		Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all 24 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, 4; Jobs are denoted by j = A, B, C, D.

	Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown. [[File:~~CompOp Wiki~~.png\|thumb\|~~509x509px~~\|'''Figure 2 ~~- 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~~.\|~~alt=~~\|~~left~~]]		Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown.
			[[File:ExampleStep1.png\|alt=\|none\|thumb\|329x329px\|'''Figure 2:''' Example Step 1 - Optimal position for any task, delay for any task, and total delay are all unknown.]]
			We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all jobs that need to be completed. In this example we know the final task will complete on day 24. Next we can calculate the delay that the final task will have given it is the last job in the sequence by subtracting the task due date from 24. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the next to last job in the sequence.
			[[File:Example2 2.png\|none\|thumb\|433x433px\|Figure 3: Example Step 2 - Determine the smallest possible delay given each possible task is placed last in the sequence.]]

	~~We begin by looking at~~ the final position in the sequence. ~~The completion date~~ for the ~~final job~~ in the ~~sequence~~ is ~~always known~~, ~~since it is the summation~~ of ~~all jobs~~ that ~~need~~ to be completed~~. In this example we know the final task will complete~~ on day 24. ~~Next~~ we can ~~calculate~~ the ~~delay that the final~~ task ~~will have given it is~~ the ~~last job in~~ the ~~sequence~~. ~~After determining~~ which job will ~~yield~~ the ~~smallest~~ delay ~~when in the~~ last ~~position, we branch from~~ that job ~~and repeat the process for the next~~ to ~~last~~ job ~~in the sequence~~.		Figure 3 shows that job C has in the final position of the sequence yields the smallest possible delay. Therefore, we branch from this path and repeat the process for the task in the second to last position. Since job C is selected to be last, and has a duration of 9 days, we know that the second to last job will be completed on day 15. From there we can once again use the due dates of each task to determine the path with the smallest accrued delay.
			[[File:Example3.png\|none\|thumb\|785x785px\|'''Figure 4:''' Example Step 3 - Branch from node C and determine which job will yeild the lowest possible delay if run second to last. It is known that this job will complete on day 15 (Time to complete job C subtracted by total time to complete jobs 24-9=15).]]

	By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.		By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.

Ms3693 at 01:04, 15 December 2021

2021-12-15T01:04:45Z

← Older revision		Revision as of 21:04, 14 December 2021
Line 72:		Line 72:
	\|Day 14		\|Day 14
	\|}		\|}
	The goal of this method is to determine the order in which the jobs should be processed on the shared resource to minimize total accrued project delay. The completion day is the summation of all job durations in a given sequence. The delay per ~~task~~ is found by subtracting a ~~task~~ due date by the completion day ~~calculated for that task~~. Total project delay is the summation of all individual ~~task~~ delays. The following table shows an example to calculate delay for one particular sequence, ABCD.		The goal of this method is to determine the order in which the jobs should be processed on the shared resource to minimize total accrued project delay. There are n! feasible solutions for a job shop scheduling problem, therefore there are 4! = 24 feasible solutions for this example. The completion day is the summation of all job durations in a given sequence. The delay per job is found by subtracting a job's due date by the job's calculated completion day. Total project delay is the summation of all individual job delays. The following table shows an example to calculate delay for one particular sequence, ABCD.
	{\| class="wikitable"		{\| class="wikitable"
	\|+Delay for Sequence (A, B, C, D)		\|+Delay for Sequence (A, B, C, D)
Line 95:		Line 95:
	\|''d<sub>4</sub> = 24 - 14 = 10''		\|''d<sub>4</sub> = 24 - 14 = 10''
	\|}		\|}
	By beginning with job A at day 0, it will be completed by day 3. This is 2 days before the job A deadline and adds no delay to the overall schedule. At completion of job B we add the 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. 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> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''		By beginning with job A at day 0, it will be completed by day 3. This is 2 days before the job A deadline and adds no delay to the overall schedule. At completion of job B we add the 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. The total project delay T is equal to the summation of the accrued delay for each jop: T = ''d<sub>1</sub>'' + ''d<sub>2</sub>'' + ''d<sub>3</sub> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''

	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, 4; Jobs are denoted by j = A, B, C, D.		Using the Branch and Bound method, we can expand upon this concept and determine the sequence yielding the smallest delay out of all 24 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, 4; Jobs are denoted by j = A, B, C, D.

	~~Show image~~ of ~~step on with explanation:~~ [[File:CompOp Wiki.png\|thumb\|509x509px\|'''Figure 2 - 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.\|alt=\|left]]~~Show image of step on with explanation:~~		Initially, the ideal sequence of the jobs, the delay for any individual job, or the total delay are unknown. [[File:CompOp Wiki.png\|thumb\|509x509px\|'''Figure 2 - 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.\|alt=\|left]]

	~~Show image~~ of ~~step~~ on ~~with explanation:~~		We begin by looking at the final position in the sequence. The completion date for the final job in the sequence is always known, since it is the summation of all jobs that need to be completed. In this example we know the final task will complete on day 24. Next we can calculate the delay that the final task will have given it is the last job in the sequence. After determining which job will yield the smallest delay when in the last position, we branch from that job and repeat the process for the next to last job in the sequence.

	~~Show image of step on with explanation:~~		By continuing to determine the lower bound at each decision level, we eventually are left with only one option left for a job to take the first position. At this point we have determined our optimal solution, or the sequence yielding the smallest possible schedule delay.

	~~Delete following after updated figures inserted above: (as well as current figure)~~

	~~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~~.

	==Applications==		==Applications==

Ms3693 at 00:43, 15 December 2021

2021-12-15T00:43:02Z

← Older revision		Revision as of 20:43, 14 December 2021
Line 72:		Line 72:
	\|Day 14		\|Day 14
	\|}		\|}
	The goal of this ~~problem~~ is to determine which ~~sequence~~ the jobs should be processed on the shared resource to minimize total accrued project delay. The following table shows an example to calculate delay for one particular sequence, ABCD.		The goal of this method is to determine the order in which the jobs should be processed on the shared resource to minimize total accrued project delay. The completion day is the summation of all job durations in a given sequence. The delay per task is found by subtracting a task due date by the completion day calculated for that task. Total project delay is the summation of all individual task delays. The following table shows an example to calculate delay for one particular sequence, ABCD.
	[[File:CompOp Wiki.png\|thumb\|799x799px\|'''Figure 2 - 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.]]
	{\| class="wikitable"		{\| class="wikitable"
	\|+Delay for Sequence (A, B, C, D)		\|+Delay for Sequence (A, B, C, D)
Line 96:		Line 95:
	\|''d<sub>4</sub> = 24 - 14 = 10''		\|''d<sub>4</sub> = 24 - 14 = 10''
	\|}		\|}
	By beginning with job A at day 0, it will be completed by day 3. 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 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. 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> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''		By beginning with job A at day 0, it will be completed by day 3. This is 2 days before the job A deadline and adds no delay to the overall schedule. At completion of job B we add the 3 days used on job A to the 5 needed for job B to get a completion time of 8 days. This yields a 2 day delay, as the deadline for job B was day 6. Finally we repeat that process for job C and job D yielding an additional 1 and 10 day delay respectively. 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> + d<sub>4</sub>= 0 + 2 + 1 + 10 = 13 days.''

	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, 4; Jobs are denoted by j = A, B, C, D.		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, 4; Jobs are denoted by j = A, B, C, D.

	Show image of step on with explanation:		Show image of step on with explanation: [[File:CompOp Wiki.png\|thumb\|509x509px\|'''Figure 2 - 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.\|alt=\|left]]Show image of step on with explanation:

	Show image of step on with explanation:

	Show image of step on with explanation:		Show image of step on with explanation:

Elaine Vallejos: /* Conclusions */

2021-12-14T04:41:56Z

Conclusions

← Older revision		Revision as of 00:41, 14 December 2021
Line 124:		Line 124:

	==Conclusions==		==Conclusions==
	JSSPs are used to optimize the allocation of shared resources in order to reduce the time and cost needed in order to complete a set amount of tasks. JSSPs account for the number of resources available, the operations needed to complete a job or task, the required order of operations, the necessary resources needed for each operation, as well as the necessary time needed with a resource for each operation in order to create an optimal schedule to complete all jobs. While this problem is used predominately for machining purposes, as the name implies, it can be adapted to be used on a variety of other cases within and outside of manufacturing. Other applications for this problem include the optimization of a computer's processing power as it executes multiple programs and optimization of automated equipment or robots		JSSPs are used to optimize the allocation of shared resources in order to reduce the time and cost needed in order to complete a set amount of tasks. JSSPs account for the number of resources available, the operations needed to complete a job or task, the required order of operations, the necessary resources needed for each operation, as well as the necessary time needed with a resource for each operation in order to create an optimal schedule to complete all jobs. While this problem is used predominately for machining purposes, as the name implies, it can be adapted to be used on a variety of other cases within and outside of manufacturing. Other applications for this problem include the optimization of a computer's processing power as it executes multiple programs and optimization of automated equipment or robots.

	==References==		==References==
	<references />		<references />

Elaine Vallejos: /* Conclusions */

2021-12-14T04:40:03Z

Conclusions

← Older revision		Revision as of 00:40, 14 December 2021
Line 124:		Line 124:

	==Conclusions==		==Conclusions==
	~~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~~.		JSSPs are used to optimize the allocation of shared resources in order to reduce the time and cost needed in order to complete a set amount of tasks. JSSPs account for the number of resources available, the operations needed to complete a job or task, the required order of operations, the necessary resources needed for each operation, as well as the necessary time needed with a resource for each operation in order to create an optimal schedule to complete all jobs. While this problem is used predominately for machining purposes, as the name implies, it can be adapted to be used on a variety of other cases within and outside of manufacturing. Other applications for this problem include the optimization of a computer's processing power as it executes multiple programs and optimization of automated equipment or robots

	~~JSSPs~~ can be ~~solved using~~ a variety of ~~methods~~ and ~~algorithms.~~

	~~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.~~

	==References==		==References==
	<references />		<references />