Assembly job shop scheduling problem (AJSP) is an extension of classical job shop scheduling problem (JSP). AJSP starts with JSP and appends an assembly stage to the completed jobs. Lot streaming (LS) technique is a process of splitting jobs into smaller sub-jobs such that successive operations can be overlapped. This paper combines, for the first time, LS and AJSP, extending LS applicability to both machining and assembly. To solve this complex problem, an efficient algorithm is proposed using genetic algorithms and simple dispatching rules. Experimental results suggest that equal size LS outperforms varied size LS with respect to the objective function.
In this paper, a job or a lot is defined as a batch of identical items or components. In order to complete a job, all of its operations should be processed on the machines. If there is assembly stage, only the completed jobs from the same bill-of-material (BOM) can be assembled for the final product. If no assembly is available, the completed jobs should be stored at the inventory. The assembly of the final product and each subassembly in the same BOM can start only when all of its components are completed. Classical job shop scheduling problem (JSP) is one of the most well-known scheduling issues and it assumes that there is no assembly stage after the job completion. One common objective of most of the available JSP models is the minimization of lateness which is defined as the penalty for completing jobs beyond its due dates. Lot streaming (LS) technique which allows splitting of jobs into sub-jobs can improve shop floor performance. As a result, lead time can be shortened and more jobs or sub-jobs may meet its due dates. In the current study, assembly job shop scheduling problem (AJSP) which appends an assembly stage to JSP has been studied. For the first time, we attempt to extend the application of LS to AJSP. To justify this study, the research objectives now become the minimization of the delay cost of the final products and the storage cost of the completed jobs and sub-jobs at the inventory. In addition to job shop features, the assembly stage should be solved in AJSP which can be regarded as an advanced version of JSP. Given the demand of a product, the relative job demands that supply the same product must be determined. If necessary, Manufacturing Resource Planning software packages can help to determine the batch sizes of components over a certain planning period. However, it is commonly assumed that the lot size is a constant, i.e. lot splitting is not allowed (e.g. [1]). Hence, we argue that the significance of LS must not be underrated in the shop floor level. For example, if a lot is composed of 4 identical items or components, there are at least 4 ways to split it: (1) {1,1,1,1} means 4 sub-jobs of size 1, (2) {1,1,2}, (3) {2,2} or {1,3}, and (4) no splitting. Hence, we have total 5 sub-job combinations. Since the combination increases significantly with the lot size and the number of jobs, it is necessary to develop an efficient algorithm. The determination of sub-job combinations is not the end of the story. After splitting jobs into sub-jobs, we need to solve AJSP which is also NP-hard. In this paper, an efficient algorithm has been proposed to solve this complex problem using genetic algorithms (GAs) and simple dispatching rules (SDRs).
In this research, an efficient algorithm is developed to solve the problem in which lots can be split into sub-lots and there is an assembly stage after JSP. To measure the algorithm performances, the late cost and inventory cost are the key indicators. To facilitate timely decision making, GA is proposed to determine the sub-job combinations (SP1) and SDRs are used to solve AJSP with all sub-lots (SP2). Using the proposed GA, a single solution can embrace the information that we need to solve the sub-lot combinations, i.e. (i) which lot should be split, (ii) the number of sub-lots, and (iii) the size of each sub-lot. In fact, this inherent advantage cannot be easily achieved by other AI or evolutionary algorithms. To examine the impact of LS on AJSP, a number of test problems have been studied under two different scenarios, i.e. with and without LS. If LS is implemented, two modes are compared, i.e. equal size (ES) and varied size (VS). According to our knowledge, there is no similar GA-based approach to examine the performances of ES and VS modes. Using SDRs, AJSP has been solved promptly. The experiment results suggest that MST with ES mode or MST-ES surpasses the others in terms of two performance measures, i.e. the minimum cost obtained in most of the test problems, and the average cost obtained over all test problems. Since there are very few LS models dedicated to AJSP, this study attempts to fill the gap and provides some insights about the usefulness of LS to assembly problems. Moreover, the proposed algorithm can be easily applied to flow shop, open shop or the mix of them. However, the current model considers only the lateness and inventory penalties that may not be practical enough to simulate the real manufacturing shop floor. Hence, regarding to the future research work, the authors would like to suggest the following issues: more penalties will be introduced like setup cost, transfer cost, WIP cost, etc. Moreover, more constraints can be incorporated, e.g. finite transfer size, finite WIP buffer, resource shortage, machine failure, etc.
