Difference between revisions of "Job shop scheduling"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 3: Line 3:
  
 
==Introduction==
 
==Introduction==
 +
The Job-Shop Scheduling Problem (JSSP) is an 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>. Resources within a JSSP are usually signified as machines (''M''), while jobs (''J'') are the activities that will need to be completed by those machines. Jobs may require the use of a specific machine, or multiple machines in a certain order. For these problems it is assumed that machines can only process one job at a time.
  
 
==Theory/Methodology/Algorithms==
 
==Theory/Methodology/Algorithms==
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem [3]]]
+
[[File:Applegate2.png|thumb|Figure 1: A Gantt-Chart representation of the job shop scheduling problem<ref name=":0" />]]
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'' [2].
+
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>.
  
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 [1]. Given these assumptions, the problem can be solved at complexity class NP-hard.  
+
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.  
  
 
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.     
 
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.     
Line 31: Line 32:
  
 
==References==
 
==References==
[1] K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.
+
[1] T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.
  
 
[2] D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.
 
[2] D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.
  
[3] T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.
+
[3] K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.

Revision as of 16:14, 28 November 2021

Authors: Carly Cozzolino, Brianna Christiansen, Elaine Vallejos, Michael Sorce, Jeff Visk (SYSEN 5800 Fall 2021)

Introduction

The Job-Shop Scheduling Problem (JSSP) is an 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[1]. Resources within a JSSP are usually signified as machines (M), while jobs (J) are the activities that will need to be completed by those machines. Jobs may require the use of a specific machine, or multiple machines in a certain order. For these problems it is assumed that machines can only process one job at a time.

Theory/Methodology/Algorithms

Figure 1: A Gantt-Chart representation of the job shop scheduling problem[1]

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[2].

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[3]. Given these assumptions, the problem can be solved at complexity class NP-hard.

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.

At least one numerical example

encouraged to have more than one

Applications

There are several ways in which the job-shop scheduling problem can be modified, often to simplify the problem, for a variety of applications.

For example, in the manufacturing industry, it is common for some 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.

This problem can also be applied to many projects in the technology industry. In computer programming, it is typical that instructions can only be executed one at a time on a single processor, sequentially. In this example of multiprocessor task scheduling, the instructions are 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.

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.

https://www.hindawi.com/journals/mpe/2020/6357394/ https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.571.9912&rep=rep1&type=pdf

Conclusions

References

[1] T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.

[2] D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.

[3] K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.

  1. 1.0 1.1 T. Yamada and R. Nakano. "Job Shop Scheduling," IEEE Control Engineering Series, 1997.
  2. D. Applegate and W. Cook. "A computational study of the job-shop scheduling problem," ORSA J. on Comput, 1991.
  3. K. Hasan. "Evolutionary Algorithms for Solving Job-Shop Scheduling Problems in the Presence of Process Interruptions," Rajshahi University of Engineering and Technology, Bangladesh. 2009.