Ph.D.s' Dissertations A Study on Job Shop Scheduling Problems considering Production Capacity Adjustment
2015.07.29 12:26
| year | 1999 |
|---|---|
| author | Daeyoung Chung |
| Keyword | job shop scheduling, production planning, operation subcontract, overtime, decomposition |
| Abstract | Reliable and timely delivery is an important factor determining the competitive strength of a manufacturing company. In some environment, keeping due date is considered as a constraint whose violation is not permitted. However, a production plan and promised due dates usually cannot be accomplished owing to diverse reasons including insufficient production capacity and unexpected events. To cope with such problems, loads are modified using alternative routing, subcontracting, overtime work, etc. Capacity adjustments are usually considered in production planning, but the plan cannot correctly reflect the limited capacities of production resources. So the intervention of human planner is inevitable to rectify the plan, but the performance of the resulting plan is usually inferior with respect to costs because the human planner does not have proper decision support tools. To make a cost efficient plan, the capacity adjustment should be considered at scheduling level. This paper deals with a job shop scheduling problem considering operation subcontract and overtime work. The problem has more decision variables and complex constraints than the pure job shop scheduling problem, which traditionally has been regarded as one of the most difficult combinatorial optimization problems. Due to the characteristic of the problem, decomposition and synthesis method is proposed to get the solution. First, the solution method starts with a traditional job shop scheduling problem with an objective of minimizing the violation of due date constraints. Second, the subcontract operations are repeatedly selected to reduce the remaining violation while minimizing the costs. At each iteration step, the overtime plans are modified to minimize the total cost of adjusting production capacities. Incidentally, the proposed solution methodology could also be utilized to solve an independent sub-problems of this type. Next, a job shop scheduling problem with an objective of minimizing maximum lateness is addressed, and an optimization method and a heuristic algorithm are developed. The optimization method transforms the problem into a series of constraint satisfaction problems (CSP), and solves the CSP until an optimal solution is found. In this research, a new variable ordering / value ordering method and an improved dichotomous search method are introduced. Being implemented with an efficient constraint propagation technique, the suggested method shows superior performance than the other existing methods. The heuristic algorithm aims to find good solutions by improving the schedules obtained by widely used dispatching rules. The algorithm is designed to incrementally reduce the maximum lateness by repeatedly re-sequencing the jobs on bottleneck machines with Carlier´s algorithm. Perceiving that the jobs spend much waiting time owing to poor sequencing decisions, the algorithm is designed to select the bottleneck machine by relaxing the capacity constraint. The suggested method was shown to improve the quality of the solution more than the critical pair-wise exchange method in a very short time. Next, a job shop scheduling problem considering operation subcontract is defined, and its solution method is suggested. The problem is decomposed into two sub-problems that are much related with each other, and so we would better not to use a sequential approach. Reflecting the relationship of the sub-problems, a solution method that deals with the sub-problems in an integrated manner is developed. In short, re-sequencing of the jobs and the selection of subcontracting operations are repeatedly conducted on bottleneck machines. To select the subcontracting operations with minimum cost, a branch and bound algorithm was developed. However, during the actual application of the algorithm, it was discovered that the maximum lateness cannot be decreased sometimes. To clear the cause of the stall and to make a way out, an algorithm that transforms the problem into a maximum flow problem is also developed. Through experiments, it is shown that the suggested solution method outperforms the conventional method and the sequential approaches. Overtime scheduling is a difficult problem that must consider the time availability of production resources. An implicit representation method that relaxes the time availability constraint and a time-based decomposition method are used to circumvent the difficulties. As a result, the original problem can be solved by successive determination of overtime production quantity in each period. To determine the overtime quantity of a period, a linear programming model is used. The LP model considers the constraints occurred by the release time of a job and the operations planned to be subcontract. The results of this study can be utilized to support the decision making of a human planner by generating a plan with minimum cost. Also this study may be considered as one of the first attempts to integrate the production planning problems and production scheduling problems. |
| c | PhD |
Download :