Job-shop scheduling

Job-shop scheduling is an important problem in computer science and operations research. It involves planning how to complete different jobs on various machines while trying to finish everything as quickly as possible. Each job is made up of several steps, called operations, that must be done in a specific order. These operations can only be done on certain machines, and only one operation from a job can be worked on at a time.

This kind of scheduling started from the idea of organizing work in a job shop, but it is used in many different areas today. It is a classic example of a combinatorial optimization problem, meaning it involves finding the best solution from many possible combinations. Scientists have studied it for a long time, and it was the first problem to be examined using a method called competitive analysis, introduced in 1966.

Understanding job-shop scheduling helps people manage tasks more efficiently in factories, computer systems, and many other places where many things need to be done at the same time on different machines.

Problem variations

Job-shop scheduling has many different versions. In some versions, machines can be duplicated or grouped together to work the same way. Machines might also need a break between tasks or have specific setup times depending on the order of jobs.

The goal of scheduling can vary too. Sometimes it’s about finishing all jobs as quickly as possible, while other times it might focus on other goals like meeting deadlines. Jobs can also have to be done in a certain order, and the processing times for each job might be fixed or change based on chances.

NP-hardness

The job-shop scheduling problem is a very difficult puzzle to solve quickly. This is because it is related to the traveling salesman problem, which is already known to be tough. In the job-shop problem, especially when setup times between tasks change depending on the order, it becomes just as challenging to solve efficiently. This means that as the number of jobs and machines grows, finding the best schedule takes more and more time.

Problem representation

The disjunctive graph is one of the popular models used for describing the job-shop scheduling problem.

In job-shop scheduling, we have a set of machines and a set of jobs. Each job needs to be done on each machine exactly once, but the order can change. We want to find a way to schedule these jobs so that the total time taken — called the makespan — is as small as possible. This means we are looking for the best arrangement where no other arrangement finishes sooner than this one.

Scheduling efficiency

Scheduling efficiency helps us understand how well machines are used when completing jobs. It looks at how much time machines are idle (not working) compared to the total time needed to finish all jobs. This helps compare how different scheduling problems use resources, even if they have different numbers of machines or jobs.

The problem of infinite cost

In job-shop scheduling, one challenge is that some solutions can have an infinite cost. This happens when machines get stuck waiting for each other, called a deadlock. For example, if two machines need to wait for the other to finish before they can start, they might never begin working, making the schedule impossible to finish.

Major results

In 1966, Graham created a method called the List scheduling algorithm to help organize tasks on machines. This method works well and was later shown to be the best possible for a small number of machines. Another method, the Coffman–Graham algorithm, was developed in 1972 for tasks that all take the same amount of time.

Many researchers have worked on improving these methods over the years. In 1992, a new method was found that worked very well, and later improvements made it even better. Today, we know the best method achieves a competitive ratio of about 1.92. In 1976, it was proven that finding the perfect solution for more than two machines is very difficult and might not be possible quickly. In 2011, new methods were found for scheduling tasks on two related machines.

Main article: Coffman–Graham algorithm

Main articles: NP-complete, P=NP

Offline makespan minimization

The offline makespan minimization problem looks at jobs that need to be done on machines, trying to finish all jobs as quickly as possible. In its simplest form, these jobs cannot be split into smaller parts. This is similar to packing items of different sizes into boxes, aiming to use the smallest possible boxes.

When jobs need multiple steps on different machines in a set order, this becomes more complex. One famous method, Johnson's algorithm, helps find the best order for jobs when there are only two machines. It works by sorting jobs based on their processing times, making it easier to schedule them efficiently.

Makespan prediction

Machine learning has been used to predict the optimal makespan of a job-shop scheduling problem without creating the full schedule. Early results suggest that this method can correctly classify small, randomly created scheduling problems about 80% of the time using supervised learning.

Example

This is an example of a job-shop scheduling problem written in a special language called AMPL. It shows how we can set up rules to organize jobs on machines. The problem uses numbers to represent how long each job takes on each machine and makes sure that jobs don't get in each other's way.

The example includes four jobs and four machines, with different times for each job on each machine, helping us see how the scheduling works.