Complexity of Loading Problems

Because of the presence of different processing orders and several alternative resources, the machine loading problem is mostly a NP-hard problem. Generally, there are two sub- problems name is: job sequence finding and operation-machine assigned associated along with the machine loading problem such are resolved in a sequential manner.

Illustration

Consider a sample problem, whereas 8 jobs are needs to be processed and all jobs contain a maximum of three operations and additionally there are whole four machines available to process the tasks. In order to search for the optimal solution, there will be a sum of 8!*2592 = 104,509,440 operation machine assign or allocations combinations.

Nonetheless, in between them few allocations are impossible like they violate the constraints concerned to machining time and tool slots. In order to decrease the complexity of machine loading problem, several assumptions are made, described as:

a)      All the information related to machines, tools and processing requirements of the jobs are known in advance.

b)      Sharing of machines and tool duplication is not allowed.

c)      Once a selected job is processing, it should be complete for all of its operations, before considering a new jobs.

d)      Transportation time of carrying the raw, semi-finished jobs is assumed to be negligible.

e)      Any particular operation of any job does not require more than one machine.