مقایسه الگوریتم ژنتیک ترکیبی و بهینه سازی ازدحام ذرات ترکیبی برای به حداقل رساندن بازه زمانی برای مونتاژ فروشگاه شغلی

Very often, studies of job shop scheduling problem (JSSP) ignore assembly relationship and lot splitting. If an assembly stage is appended to JSSP for the final product, the problem then becomes assembly job shop scheduling problem (AJSSP). To allow lot splitting, lot streaming (LS) technique is examined in which jobs may be split into a number of smaller sub-jobs for parallel processing on different stages such that the system performance may be improved. In this study, the system objective is defined as the makespan minimization. In order to investigate the impact of LS on the system objective under different real-life operating conditions, part sharing ratio (PSR) and system congestion index (SCI) are considered. PSR is used to differentiate product-specific components from general-purpose, common components, and SCI for creating different starting conditions of the shop floor. Both PSR and CSI are useful as part sharing (also known as component commonality) is a common practice for manufacturing with assembly operations and system loading is a significant factor in influencing the shop floor performance. Since the complexity of AJSSP is NP-hard, a hybrid genetic algorithm (HGA) and a hybrid particle swarm optimization (HPSO) are proposed and developed to solve AJSSP in consideration of LS technique. Computational results show that for all test problems under various system conditions, HGA can significantly outperform HPSO. Also, equal-sized lot splitting is found to be the most beneficial LS strategy especially for medium-to-large problem size.

Given a number of machines and jobs, each operation of a job must be processed on one of the machines in a predetermined and fixed sequence in a traditional job shop environment. A job is deemed as “completed” once all of its operations are successfully processed by the corresponding machines. Usually, there is no mutual relationship between jobs in the same shop floor. Also, a job which usually contains a batch of identical items cannot be split into smaller pieces. Therefore, a batch must be wholly moved among machines even some items of the batch have been already processed. In reality, these two restrictions are sometimes invalid. The first restriction assumes that each job is independent and the second assumes that each job cannot be split. To relax the first restriction, an assembly stage is attached to the job shop such that there is assembly relationship between jobs after completion at JSSP stage. Hence, the bill-of-material (BOM) of all products must be constructed to define the root components (jobs) of a product. With the BOM, the assembly relationship between different jobs can be created. If there is no part sharing, only jobs from the same BOM can be assembled. In contrast, part sharing allows job assembly from distinct BOMs. To allow job splitting, lot streaming (LS) technique is considered to remove the second restriction. With LS, it is a must to make three LS decisions for each job: (1) whether the job will be split (binary: yes or no), (2) the sub-job number, and (3) the size of each sub-job. In order to simulate a realistic shop floor, a 4-level part sharing ratio (PSR) and a 4-level system congestion index (SCI) are applied. PSR is applied to define the degree of component commonality among different products, i.e. the higher the PSR, the higher the probability that a component is shared by more than one product. SCI is examined to simulate different initial operating condition of a system, i.e. the higher the SCI, the higher the system congestion will be. By considering different levels of PSR and CSI, the impact of LS on makespan minimization can be better examined. As the problem complexity is NP-hard, a hybrid genetic algorithm (HGA) and a hybrid particle swarm optimization (HPSO) are proposed and developed to minimize the makespan of JSSP with assembly stage (AJSSP). Computational experiments are performed to examine the goodness of HGA and HPSO with respect to the objective function, and to obtain the best LS strategy under various system conditions. This paper is organized as follows. The literature review is given in Section 2. In Section 3, the problem background and formulations are presented. The two hybrid algorithms are depicted in Section 4. In Section 5, computational results are reported and discussed. Conclusions are made together with future research direction in Section 6.

In this paper, two hybrid evolutionary algorithms, HGA and HPSO, are proposed and developed to minimize the makespan in AJSSP environment with LS technique. To enhance the complexity and usefulness of the research model, two real-life system conditions are considered: part sharing ratio (PSR) and system congestion index (SCI), each with 4 levels. An experiment has been launched to compare the performance of HGA and HPSO in minimizing the system makespan under different operating conditions. Computational results suggested that HGA is significantly better than HPSO under various operating conditions with and without LS. The result has also shown the negative impact of SCI on the system makespan in AJSSP environment. However, no significant correlation can be observed between PSR and system makespan. If LS is applied, it is always more beneficial to split lots into equal-sized sub-lots. Nevertheless, the tradeoff is to having more sub-lots in the system and it may greatly increase the cost of material handling and setup since there are more additional movement and loading/unloading if n* is much greater n. According to the author's knowledge, there is no similar research dedicated to AJSSP with LS under various system conditions in consideration of makespan minimization, and therefore, the current study may be considered as the first of its kind in this niche area. A limitation of the proposed model is that it is not directly applicable to situations in which the lot size is not discrete or the size is fixed in terms of length, weight, etc. – for example, in the production of printed circuit board (PCB), a lot is usually a roll of thin copper sheets measured in weights. In order to further the current work, more complicated product structure and bigger test problems will be investigated in future studies. Rather than a single objective, multiple yet conflicting objectives (such as makespan and lateness) will be jointly considered so as to examine the impact of LS on system measures which are in collision. Also, more hybrid evolutionary algorithms such as ant colony optimization (ACO), simulated annealing (SA), will be adapted, applied and compared with HGA and HPSO.