The job shop problem is an optimization problem in computer science in which ideal jobs are assigned to resources at particular times. It is as follows: There are given n jobs J1, J2,...,Jn of varying sizes, which need to be scheduled on m identical machines, while trying to minimize the make span. The make span is the total length of the schedule (that is, when all the jobs have finished processing). It is mostly presented as an online problem, that is, each job is presented, and the online algorithm needs to make a decision about that job before the next job is presented. Job shop scheduling is concerned with finding a sequential allocation of competing resources that optimizes a particular objective function [1]. There are many variations of the problem exist, which can be summarized as follows: • Machines can be related, independent, equal • Machines can require a certain gap between jobs • Machines can have sequence-dependent setups • Objective function can be to minimize the make span, the Lp norm, etc • Jobs may have constraints, for example a job i need to finish before job j can be started. • Jobs and machines have mutual constraints, for example, certain jobs can be scheduled on some machines only.

Full text: IJEIR_839_Final.pdf