A batch splitting method for a job shop scheduling problem in a materials requirements planning environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the set-up before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as on many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there many be an optimum batch size considering trade-off between solution and tracability. The current study is the result of an attempt to find an acceptable solution when the production requirement from an MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called ‘modified shifting bottleneck procedure’ is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.