טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentKraus-Albo Chen
SubjectMulti Objective Lot-Splitting for Reentrant Job-Shop
DepartmentDepartment of Industrial Engineering and Management
Supervisors Mr. Michael Masin
Professor Michal Penn
Full Thesis textFull thesis text - English Version


Abstract

Modern production lines require advanced scheduling and control tools that enable diverse machines to perform different production processes efficiently, in tandem or consecutively, according to the production stages. A production line with a product that is processed several times on the same machine, at different production stages, is called a reentrant line. Lot-splitting methods split initial large lots into smaller sublots and, therefore, can enhance performance on all production environments, and in particular on the reentrant environment. Wafer fabrication plants are the preeminent example of cutting edge production environments.

This research deals with lot-splitting and scheduling of multiple products in an N-product M-machine reentrant job-shop environment. The objective is to minimize the makespan and the average flowtime simultaneously. We utilized splitting of the initial lots into sublots for achieving our objective. The non-dominated solutions, relative to both objectives, form an Efficient Frontier (EF).   

Since the general problem is difficult (NP-hard), several heuristics methods were developed: (i) A known algorithm for the flow-shop (FS) lot-splitting problem (by Kalir and Sarin) is adapted to fit the job-shop production environment; (ii) a Cross-Entropy (CE) algorithm is extended for solving multi-objective problems and adapted to our lot-splitting problem; and (iii) Trade-Off Programming (TOP) based algorithms are developed to fit the multi-product property.

Experiments are conducted in order to estimate the CE algorithm parameters, to compare the performance of the proposed algorithms and to evaluate the problem characteristics. The algorithms are compared to the optimal EF for small- to medium-sized problems. The results show that the CE and TOP algorithms outperform the FS based algorithm by 6% to 9% and achieve near optimal results for small- to medium-sized problems, and by 12% in larger problems. In addition, it is interesting that even though in all our experiments the number of solutions on the optimal EF is relatively small, eight on average, the trade-off between makespan and average flowtime may reach tens of percents.