Masters' Theses Job Shop Scheduling for Minimizing the Sum of Earliness and Tardiness
2015.07.29 12:31
| year | 2000 |
|---|---|
| author | Dongsu Park |
| Keyword | job shop scheduling, tardiness, earliness, SBP |
| Abstract | In the face of increasing international competition, production planning and control is becoming more and more important for manufacturers. Short delivery times, punctual delivery, productivity improvement and low inventories play key roles in the competitiveness of a company. In many companies, the weighing of objectives of their production control has shifted from maximizing resource utilization to achieving simultaneously punctual delivery to customers, productivity improvement and low inventories. But previous researches on scheduling problem mainly focused on minimizing regular objectives such as makespan, maximum lateness, and so on. Under the influence of JIT(Just In Time) philosophy, recently some researchers have begun to consider earliness. However most of them dealt with single machine problem, and there is few research on job shop problem. This paper deals with minimizing the weighted sum of earliness and tardiness in a job shop. This problem relates to be so-called non-regular . Non-regular scheduling problem is decomposed into sequencing the jobs on each machine and setting the start/finish time of a job, given job sequences. In this study, we sequence the jobs on each machine using SBP(Shifting Bottleneck Procedure) and set the start/finish time of a job using a heuristic. Two methods are used to select one machine as bottleneck : ⑴ method(SBP1) using branch and bound algorithm combined with timing heuristic and ⑵ method(SBP2) using the lower bound of single machine problem. We developed a branch and bound algorithm to solve single machine problem with different ready time and partial sequence and proposed a method for calculating lower bound of that problem. Experimental results show that single machine problems are solved within 1 seconds by the proposed branch and bound algorithm combined with timing heuristic and the solutions deviate from optimum by less than 1% and as for job shop problem, both the two proposed methods generate quite better solutions tha n dispatching rule within 2 minutes although their solutions deviate much from optimum for small-sized problem |
| c | MS |
Download :