Ph.D.s' Dissertations An Improved Scheduling Heuristic Based on Batch Splitting Method for The Job Shop Scheduling Problem
2015.07.29 12:13
| year | 1996 |
|---|---|
| author | Hanil Jeong |
| Keyword | Batch Splitting, Improving Schedule, Job Shop Scheduling, Before-Arrival Family Setup Time, Branch and Bound |
| Abstract | The job shop scheduling problem has been a major target for many researchers. However, most of the past studies assumed that a job consists of only a single part. With this assumption, the master production schedule and MRP output must be modified when production requirement from MRP( Material Requirement Planning )for a planning period exceeds the capacity of production system. In addition to that, a real factory is full of unexpectedness and dynamics. Due to such dynamic nature of shop floor, the requirements for production volume and due date can not easily be satisfied under the assumption that a job consists of a single part. In many cases of real manufacturing environment, however, a job does not consist of a single part but a set of parts of same type, so-called a batch. We can alleviate the problems mentioned above by considering characteristics of batch. That is to say, if we allow each part which constitute a batch to be processed independently, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs of smaller processing time. However, then, the size of the scheduling problem would become too large to be solved in practical time limit, and the clerical work will also increase to handle the increased number of production orders. And so, there may be an optimum batch size considering trade-off between better solution and tractability. We propose an improved scheduling algorithm when a job consists of a batch. For this algorithm, we try to minimize makespan or maximum lateness for job shop scheduling problem considering before-arrival family setup time, transportation time, release date and due date. Our scheduling algorithm can be divided into two parts. The first part selects a batch to be splitted and splits it into smaller batches. The second part solves the new job shop scheduling problem with smaller batches. The batch splitting algorithm selects a batch to be splitted based on information of lateness and idle time, and then its size is determined by batch splitting strategy. The proposed job shop scheduling algorithm contains a new branch and bound algorithm to minimize makespan for single machine sequencing problem considering before-arrival family setup time, release date and delivery time. This algorithm starts with obtaining a single machine sequencing problem using the characteristic values of operation from disjunctive graph which represents job shop scheduling problem. Final solution is obtained by applying proposed single machine sequencing algorithm iteratively. The proposed new branch and bound algorithm for single machine sequencing problem consists of five modules, they are branching, determining precedence, modifying characteristic values of operations, generating heuristic solution and calculating lower bound modules. Experimental results show that the proposed single machine sequencing algorithm finds an optimal solution within small time limit. The proposed job shop scheduling algorithm shows better performance than tabu search, simulated annealing and genetic algorithm, and error rates compared to optimal solution is low. The batch splitting algorithm shows that only a few split can improve schedule considerably, and we can handle dynamic events more elegantly by this algorithm. |
| c | PhD |
Downlaod :