Job Sequencing in operation research

job sequencing : introduction

In this section, we delve into the challenge of arranging the order in which several tasks must be executed across various machines to optimize efficiency and maximize productivity. When confronted with a scenario involving n tasks distributed among m machines, the objective is to identify the most optimal sequence of tasks. This sequence aims to minimize the overall elapsed time, encompassing the duration from the initiation of the initial task to the conclusion of the final task.

Imagine a scenario where either 2 or 3 tasks need to be executed across 2 or 3 machines. In such cases, job sequencing can be efficiently handled through enumeration. However, as the number of tasks and/or machines escalates, the complexity of the problem increases significantly, rendering the enumeration method impractical and unsuitable for resolution.

Consider a scenario where there are n machines and m jobs to be scheduled. In such a case, there are potentially (n!) ^m sequences to explore. For instance, when n equals 5 and m equals 5, the number of potential sequences amounts to (5!)⁵, resulting in a staggering 25,000,000,000 possible permutations. Clearly, exhaustively examining all these sequences to determine the optimal one is time-consuming and impractical. Therefore, it becomes imperative to seek alternative methods that offer a more efficient approach to identifying the optimal sequence.

basic terminology

Here are the basic terminologies related to job scheduling and sequencing:

1.Task: A specific unit of work that needs to be accomplished within a defined timeframe.

2.Device: A tangible or virtual entity with the capability to perform tasks or operations.

3.Task Sequencing: The process of organizing the order in which tasks or jobs are executed.

4.Device Sequencing: Determining the order in which tasks are processed across different devices.

5.Optimal Order: The most effective arrangement of tasks or jobs that minimizes overall time or maximizes productivity.

6.Time Elapsed: The duration between the initiation of the first task and the completion of the last.

7.Timetable: A structured plan detailing the start and finish times for each task on each device.

8.Scheduling Method: A systematic approach used to establish the sequence or timetable of tasks on devices, often with the goal of optimizing specific objectives like minimizing total completion time or maximizing resource efficiency.

9.Total Completion Time: The cumulative duration needed to finish all tasks within a given timetable.

10*Sequential Constraint: A condition stipulating the order in which certain tasks must be executed relative to others.

11*Priority Level: A measure of the relative importance or urgency assigned to a task, influencing its order of execution.

12*Downtime: The period during which a device remains inactive or unused due to scheduling gaps or inefficiencies. These terms serve as a framework for understanding and discussing challenges related to job scheduling and sequencing.

principal assumptions

Here are the principal assumptions related to job scheduling and sequencing:

1.Resource Limitation: It is presumed that there exists a finite number of machines, tools, or resources available for the execution of tasks.

2.Task Independence: Tasks are considered to operate independently of each other, implying that the completion of one task does not hinge on the status or progression of another task.

3.Fixed Task Duration: Within many scheduling models, it is posited that each task demands a fixed duration for completion once it is initiated.

4.Deterministic Context: The scheduling environment is envisioned as deterministic, signifying that parameters such as task processing times and resource availability are known with certainty and remain stable.

5.Precedence Constraints: Certain tasks may exhibit dependencies or precedence constraints, dictating that specific tasks must be accomplished before others can commence.

6.Single Optimization Objective: Many scheduling algorithms concentrate on optimizing a singular objective, such as minimizing the overall completion time or maximizing resource utilization.

7.Continuous Operation Assumption: Scheduling models commonly assume uninterrupted operation of machines or resources, though real-world scenarios may involve intervals for breaks or maintenance.

8.Homogeneous Resource Pool: The machines or resources designated for task execution are typically presumed to be homogeneous, possessing similar capabilities and performance attributes.

9.Static Environment: The scheduling problem is often depicted as static, suggesting that parameters such as task arrival times, durations, and resource availability remain constant over time.

10*Deterministic Task Durations: Task durations are typically assumed to be deterministic, indicating that the time required for each task's completion is definitively known and does not fluctuate. These principal assumptions form the cornerstone of the conceptual framework for the development and analysis of job scheduling and sequencing methodologies.

types of job sequencing

Different job sequencing problems emerge across various fields, and it's acknowledged that not all of them can be resolved definitively. In this context, we'll examine four distinct types of job sequencing problems:

n jobs are to be processed on 2 machines, say, machine A and machine B in the order AB. This means that each job is to be processed first on machine A and then on machine B
n jobs are to be processed on 3 machines A, B and C in the order ABC, i.e., first on machine A, second on machine B and third on machine C.
n jobs are to be processed on m machines in the given order
2 jobs are to be processed on m machines in the given order.

Processing of n Jobs through 2 Machines

Consider a scenario where a set of n jobs needs to be executed on two machines, designated as A and B. Each job must undergo a specific sequence of operations in a fixed order; any deviation from this sequence is prohibited. Once a job completes its processing on machine A, it is subsequently routed to machine B. Should machine B be occupied at that time, the job is queued for processing. Jobs in the queue are handled based on the FIFO (first in, first out) principle.

Let's denote:
- A_i as the processing time required for the ith job on machine A.
- B_i as the processing time required for the ith job on machine B.
- T as the total elapsed time.

The objective is to determine the most efficient sequence for processing the n jobs on machines A and B to minimize the total elapsed time (T). Below, we introduce a methodology developed by Johnson and Bellman aimed at identifying an optimal sequence.

Step 1 Select the minimum processing time out of all A_i ’s and B_i ’s. If it is A_r then do the rth job first. If it is Bs_s then do the sth job at last.

Step 2 If there is a tie in selecting the minimum of all the processing times, then such a situation is dealt with the following three ways:
(i) If the minimum of all the processing times is A_r , which is also equal to B_s , that is, min(A_i ,B_i ) = A_r = B_s , then do the rth job first and sth job at last.
(ii) If min(A_i ,B_i ) = A_r , but A_r = A_k , i.e., there is a tie for minimum among A_i ’s, then select any one.
(iii) If min(A_i ,B_i ) = B_s , but B_s = B_t , i.e., there is a tie for minimum among B_i ’s, then select any one.

Step 3 Now, eliminate the job which has already been assigned from further consideration, and repeat steps 1 and 2 until an optimal sequence is found.

note : Johnson's algorithm focuses on minimizing the downtime of machines. It has been demonstrated that the most efficient sequence for n jobs, to be executed sequentially on both machine A and machine B in the order AB, inherently requires identical job ordering on each machine. Optimal total elapsed time is achieved when the job sequence remains consistent across both machines.

Example : Suppose that there are five jobs, each of which has to be processed on two machines A and B in the order AB.
Processing times are given in the following table:

Job	machine a	machine b
1	6	3
2	2	7
3	10	8
4	4	9
5	11	5

Determine a sequence in which these jobs should be processed so as to minimize the total processing time.

Solution:The minimum time in the given table is 2, which corresponds to job 2 on machine A. So the allocation of jobs will start as

Now, we eliminate job 2 from further consideration. The reduced set of processing times is as follows:

Job	machine a	machine b
1	6	3
3	10	8
4	4	9
5	11	5

Now,the minimum time is 3 for job 1 on machine B. Therefore, this job would be done at last. The allocation of jobs till this stage would be

. After deletion of job 1, the reduced set of processing times is as follows:

Job	machine a	machine b
3	10	8
4	4	9
5	11	5

Similarly, by repeating the above steps, the optimal sequence is obtained as

On the basis of this optimal sequence, the minimum elapsed time is obtained from the following table as 36 hours.

job	machin a		machin b
job	time in	time out	time in	time out
2	0	2	2	9
4	2	6	9	18
3	6	16	18	26
5	16	27	27	32
1	27	33	33	36

Further, idle time for machine A = total elapsed time − time when the last job is out of machine A = 36−33 = 3 hours. Idle time for machine B = time at which the first job in a sequence finishes on machine A + (time when the ith job starts on machine B) − (time when the (i -1)th job finishes on machine B). Therefore, idle time for machine B = 2 + (9 − 9) + (18 − 18) + (27 − 26) + (33 − 32) = 4 hours