| In this research, two heuristics will be developed to solve practical job shop problems with different objectives. Cycle-Jump Tabu Search (CJTS) is a TS based heuristic used to solve problems with makespan as the objective. All TS research regarding this objective used a large number of iterations to generate a solution. This is impractical for real problems presented in database systems (MRP-II). The essential idea of CJTS is to develop a new rule to define the neighborhood of a solution, so that the search of TS may be effectively guided and the number of iterations for convergence will be significantly reduced. The other heuristic, Early-Tardy Inversion Method (ETIM), is developed to solve the problems with total earliness and tardiness as the objective. Although a few dispatching rules have been developed for each of the objectives such as tardiness, earliness, and number of tardy jobs, all of them performed poorly for the candidate objective, total earliness and tardiness. The idea of ETIM is to generate an initial schedule by using a chosen dispatching rule, then starting from this schedule, repeatedly adjust the start dates of early and tardy jobs to regenerate a schedule so as to minimize the objective value. In this study, ETIM will be applied to several different types of problems (e.g., tight due-date problem, loose due-date problem, and "ambiguous" due-date problem). It is expected that, like the research on earliness or tardiness, a rule for choosing different dispatching rules to work with ETIM can be identified. Due to the data of job shop accessed from a real environment (e.g., Vickers Inc. in Jackson, Mississippi State), the related production information can aggregate many mega-bytes of data. A shop floor control system, SFCS-MSU, is developed by constructing a database system. All of the test problems in this research are selected from the instances in the database of SFCS-MSU. The performance of both heuristics, CJTS and ETIM, will be thoroughly evaluated and the results of this research will be applied to SFCS-MSU. |
