Job-shop scheduling

Job-shop scheduling is an important problem in computer science and operations research. It helps plan how to finish different jobs on many machines as fast as possible.

Each job has several steps, called operations. These steps must be done in a specific order. Only certain machines can do each step, and only one step from a job can be worked on at a time.

This kind of scheduling began with organizing work in a job shop. Today, it is used in many areas. It is a classic example of a combinatorial optimization problem. This means finding the best solution from many possible choices. Scientists have studied it for a long time. It was the first problem to use a method called competitive analysis in 1966.

Learning about job-shop scheduling helps people manage tasks better in factories, computer systems, and many other places with lots of work to do.

Problem variations

Job-shop scheduling has many different versions. In some versions, machines can be grouped together to work the same way. Machines might also need a break between tasks.

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 meeting deadlines. Jobs can also have to be done in a certain order.

NP-hardness

The job-shop scheduling problem is a very hard puzzle to solve quickly. This is because it is related to the traveling salesman problem, which is already known to be tough. When setup times between tasks change depending on the order, it becomes even harder to solve fast. As more jobs and machines are added, finding the best schedule takes longer and longer.

Problem representation

The disjunctive graph is a common way to show the job-shop scheduling problem.

In job-shop scheduling, we have machines and jobs. Each job must be done on each machine once, but the order can change. We want to plan these jobs so that the total time — called the makespan — is as short as possible. We are looking for the best plan where no other plan can finish faster.

Scheduling efficiency

Scheduling efficiency helps us see how well machines are used when doing jobs. It checks how much time machines sit idle, not working, compared to the total time to finish all jobs. This lets us 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, sometimes the plan can end up costing forever. This happens when machines wait for each other too long, called a deadlock. For example, if two machines each need the other to finish first, they might just keep waiting and never start. This makes it so the work can never really begin.

Major results

In 1966, Graham made 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 for a small number of machines. Another method, the Coffman–Graham algorithm, was made 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 it was made even better. Today, we know the best method works almost as well as possible. In 1976, it was proven that finding the perfect solution for more than two machines is very difficult. 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. The goal is to finish all jobs as quickly as possible. In its simplest form, these jobs cannot be split into smaller parts. This is like packing items of different sizes into boxes, trying to use the smallest 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 can help guess the best makespan for a job-shop scheduling problem without making the whole schedule. Early tests show that this way works well for small, made-up problems about 80% of the time using a learning method called 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. This helps us see how the scheduling works.