BATCH SCHEDULING FOR A THREE-STAGE HYBRID FLOW SHOP TO MINIMIZE TOTAL ACTUAL FLOW TIME

• Main Author: Maulidya, Rahmi
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/47048
• Institution: Institut Teknologi Bandung

The so called three-stage hybrid flow shop consists of machining, assembly and differentiation stages producing different product types. The machining stage has parallel independent (unrelated) machines each of which produces common and unique components. The common components are the same for all products processed in batches and the unique components are specific for each product processed in a-one-by-one. In the assembly stage, the completed common and unique components of a product are assembled following the assembly structure of its product. The assembled part received the final process to become a certain type of product. The processing of all products are finished at their multiple due dates. The problem in this dissertation is to find a schedule for the three stage flow shop system. The objective in this dissertation is to minimize total actual flow time considering a condition of common and multiple due dates. Actual flow time is defined as the interval time of parts in the shop from the arrival time until their respective due dates. This criterion impacts on the arrival times of parts that can be fit to the starting times of processing the part (not in time zero) and the schedule is generated from its respective due date so that the production that has already planned in the planning horizon meet its due date. This dissertation starts with the development of a non linear programming model for job scheduling using backward approach considering common due date, and continues with the linear programming model (Model 1A). Next, we develop a non linear programming model and a linear programming model for batch scheduling considering common due date (Model 2). In this dissertation, we also develop a model for scheduling problem considering a single assembly level of the common component which produced in batch and the unique component which produced individually (Model 3A), also considering a multi assembly level (Model 4A), both are set to meet their common due date. The fact that each order has its own due date. So, we develop Model 1B from Model 1A, Model 3B and Model 3C from Model 3A, and Model 4B from Model 4A that consider to meet multiple due dates. In each model, we propose heuristic algorithm using shortest processing time (SPT) and variable neighbourhood descent method with insert and swap move operators. SPT method has the ability to determine the sequence in increasing order of the processing time and it is suit to give an initial solution. Furthermore, VND method optimizes the solution with a deterministic way and fix pattern to generate sequences. Insert and swap move operators are selected among others for their simplicity in generating sequences by shifting one position forward along the solution, and next, the best solution is optimized again by swapping two position respectively. Model 1 is developed by changing the three-stage forward scheduling into the three-stage backward scheduling considering the due date and the objective function of total actual flow time. The resulting model for common due date condition are Model 1A (non linear), Model 1A (liniear) as a result of a linearization process of the minimum function and the two binary multiplication equations, and an heuristic algorithm. The linearization process has caused lessen computation time and number of iterations for Model 1A, and the problems of J=12 and J=16 can be solved within two hours. The numerical analysis of Model 1A shows the number of machines in differentiation stage give significant TAFT value than the number of machines in machining stage. Model 2 begins with developing Model 2A for batch scheduling at the machining stage and job scheduling at the assembly and differentiation stage. The linearization process of Model 2A is succeded to linearize the constraints, except for the objective function that still has the multiplication of two decision variables. However, the result shows the lessen number of iterations and computation time. In the proposed algorithm, the batch sequence is obtained by grouping jobs of the same type following the job sequence. The formulation continues with Model 2B for batch scheduling at the three stages of the system. In Model 2B, there are two scenarios such as scenario for the same number of batches for all stages and scenario for different number of batches for every stage of the system. The result shows that the scenario for different number of batches gives the lower total actual flow time than the other scenario. In Model 2B, the heuristic algorithm that similar to Model 2A is proposed. The differences for each scenario are in generating the batch sequence from the job sequence for each stage and the same for all stages. The result show that the pattern of batch sizes are different between the optimal model and the proposed algorithm. Model 3A is developed for common and unique parts at the machining stage and job scheduling at the assembly and differentiation stage. The optimal model is developed in the presence of common parts that is grouped in batches and unique parts which are processed one by one as jobs. Batches and jobs are arranged in a new order that is optimal to produce the minimum total actual flow time. The proposed algorithm uses the previous job sequence to represent the processing of unique part and the previous batch sequence to represent the processing of common parts and generates a sequence known as the job and batch sequence. Then, Model 3A is developed to Model 3B considering multiple due dates condition of processing the different types of products. Model 4A is developed from Model 3A which consists of batch scheduling for common parts and job scheduling for unique parts at the machining stage, job scheduling at the assembly stage for assembly operations with complex assembly structures consisting of more than one assembly level, and batch scheduling at the differentiation stage. The optimal model is developed for the batches of common parts and the jobs of unique parts originating from the same machine at the machining stage as a pair of unique and common part, then the pairs are assembled with other pairs in several assembly levels at the assembly stage, and at the Differentiation Stage, the assembled parts for the same product type will be grouped in batches for the final processed. Numerical analysis shows the different sequence approach give minimum TAFT value than the same sequence approach. Model 1B, Model 3B, Model 3C and Model 4B are developed for scheduling problems with a condition of multiple due dates. In Model 1B, each product is represented by a job that has a different due date based on the order agreement. The optimal model is developed based on the due date for each job and job can only be processed if the previously scheduled job does not take the job processing time until its due date. The proposed algorithm begins with grouping jobs based on the order of due dates and the sequence is generated within the group of due date for the first time. Model 3C is developed from Model 3B considering batch scheduling at the differentiation stage with a condition of multiple due dates. In the model, the respective due date of batches are defined as the minimum due date of jobs belongs to a batch. The fact that the number of batches and the batch sizes are different at the machining and the differentiation stages, the objective of total actual flow time will be obtained from different number of batches. The proposed algorithm is different for the differentiation stage where we applied the batch scheduling and we use the same job sequence of all stages to generate the batch scheduling. Model 4B is developed from Model 4A with a condition of multiple due dates. The optimal model is developed based on the multiple due dates. At the differentiation stage, the due date is determined based on the minimum due date of jobs in a batch. The objective function of the total actual flow time will be counted for every part produced at the machining stage until the particular due date to produce the final product. The validation is conducted using Model 4A for the real cases of platen and roller assy industry. We made some changes in Model 4A to add some processes between two assembly operations and some processes at the end of the machining stage. The result of validation shows that the optimal model can solve the problem of small instances and the algorithm can solve the problem of bigger solutions with the minimum TAFT value.