Home / Summaries / Planning and Scheduling / sb-machine-times

Job Shop scheduling - Practical job shop scheduling

37 important questions on Job Shop scheduling - Practical job shop scheduling

What does the SB procedure do?

The SB procedure decomposes the job shop problem into a series of single machine scheduling problems.
It schedules machines one by one focuses on the bottleneck machines.

In the SB procedure what are conditions are proposed for G?

G may not contain directed cycles.

What is the decomposition principle

We only adjust

G
specify resulting conflict sets
characterize the resulting machine scheduling problem

What are [9] extensions for the SB procedure?

Release and due date;
Set-up times;
Parallel machines;
Transportation times;
Unequal transfer and production batches;
Multiple resources;
Downtimes;
Convergent and divergent job routings;
Open shops

Why are release and due dates considered an extension of the SB?

It is not a realistic assumption that all jobs become available at the same time.

Is dealing with job release and due dates an online/offline problem?

No considered conflict sets and machine scheduling problems are considered. Only the weight of some arcs in G are changed or arcs are added. Therefore it is an offline procedure.

Why are setup times considered an extension of the SB?

A machine may have a set-up time before it can process the next operation. Tool switching or cleaning. No operations can be processed.

What is a solution for the setup times?

Adjusting/giving weight to the machine arc during the SB procedure.

Is dealing with setup times an online/offline problem?

The SB procedure deals with setup times by changing the weight of the machine arcs in G and having an algorithm for the machine scheduling subproblems with setup times.

Why is parallel machines considered an extension of the SB?

Because in practice operations may sometimes be performed by any machine from a group of parallel machines. Operations are assigned to one of the machines and accordingly sequenced on this machine.

Is dealing with parallel machines considered to be an online/offline problem?

If the processing times are machine-dependent, then this requires online changing of node weights.

Why is transportation times considered an extension of the SB?

Because in practice it may be impossible to start the next operation immediately due to the transportation of the machine.

What do we have to do when transportation capacity is limited and how do we do this?

Transportation has to be scheduled as well
Model transportation with vehicles that can only transport one job at a time as a parallel-machine group with setup times. The vehicles are seen as a machine in this group with the # of vehicles seen as a machine in this group.

Why are unequal transfer and production batches an extension of SB?

A job may be an order to produce a batch of b identical products not just a single product.

What is a production batch?
Assumption made

B identical products that need to be processed consecutively on each machine. Assumption: processing times are continuously.

Is dealing with unequal transfer and production batches an online/ofline problem?

Ofline

Why are multiple resources considered an extension of SB?

Often an operation needs two or more resources simultaneously for its processing. Besides a machine, an operation may need a pallet on which it must be fixed, certain tools or an operator at the machine.

How is the issue of multiple resources modelled?

Through adding disjunctive edges to G that connect all operations that need the same resource.

What are the 2 approaches to deal with multiple resources and when do you apply them?

Centralized approach, small amount of resources
Decentralized approach, large amount of resources

Explain the centralized approach (multiple resources)

Every resource is seen as a machine that needs to be scheduled. There is no differentiation between machines and jobs. Every resource becomes a bottle neck.

When is the decentralized approach (multiple resources) used, give an example

When the number of additional resources is large. Such as the FMC.

What is the approach of the decentralized approach (multiple resources)?

There is a seperate algorithm to deal with the big amount of resources. (Algorithm for scheduling the FMC).

Why is downtime considered an extension of the SB?

Because machines in a shop may have different availability times or unavailable during maintenance.

What are [2] types of downtime distinguished?

Preemptive, operation starts before and finishes after downtime.
non-preemptive, operation completes process before or after downtime. (maintenance)

How is downtime modelled?

As operations that need to be processed in a prespecified interval.

Is dealing with downtime an online/ofline problem?

Online (preemptive and non-preemptive)

Why are convergent and divergent jobs considered an extension of the SB?

Because problems are often not a chain of operations.

What is a convergent job?

Occurs when some components are assembled

What is a divergent job?

Starting with a piece for example a metal sheet that needs some cleaning and surface treatment. After cutting the different parts of the sheet have their own routings through the shop.

How is a convergent/divergent job modelled?

By allowing G to have multiple ingoing and outgoing arcs.

Is dealing with convergent/divergent jobs an online or offline problem?

Offline

On what do SB procedures outperform priority rules?

Maximum lateness
mean tardiness

On what does the priority rule outperform SB?

Number of late jobs

Why are open shops considered an extension of the SB?

Because in real-life the sequence in which jobs can be processed does not necessarily have to be fixed although they cannot be processed simultaneously.

How can open shops be modelled?

By introducing for each job a single artificial machine on which the operations of this job must be processed.

As what can open shops be seen?

As a special case of multiple resource problems.

What is a delayed precedence constraint?

A precedence constraint between two operations with the additional constraint that there is a certain delay between these two operations.

The question on the page originate from the summary of the following study material:

Planning and Scheduling

View summary

A unique study and practice tool
Never study anything twice again
Get the grades you hope for
100% sure, 100% understanding

Remember faster, study better. Scientifically proven.

Topics that are related to Job Shop scheduling - Practical job shop scheduling

Variability management