یک الگوریتم برای به حداقل رساندن شاخص ضربه ی پنالتی زودکرد وزنی در تولید کارگاهی مونتاژ

This paper addresses the problem of minimizing the weighted earliness penalty in assembly job shops. A job in the shop is assumed to have a tree product structure consisting of components and subassemblies and that each component or subassembly may need additional processing before it can mate with other parts. As is typical in just-in-time production, no tardy job is allowed. Because of the computational time intensity associated with the problem, a heuristic was developed to solve the problem. Optimality conditions were derived and used in the development of the heuristic. The heuristic decomposes the problem into several single machine problems. Solutions to the single machine problems were used to construct the solution to the original problem. The effectiveness of the heuristic was evaluated by solving a set of test problems. The results of the test problems demonstrated that the heuristic is effective in solving the problem.

In this paper, the problem of minimizing the weighted earliness penalty in assembly job shops is addressed. An assembly job shop refers to a shop that involves both processing and assembly operations. It is assumed that each product has a tree structure of components and subassemblies that assemble together to build up the end product. For the sake of conciseness, we draw a distinction between a job and a product in the rest of the paper. A product is the item ordered by a customer or the item that is shipped from the shop to a customer. A product is composed of components and subassemblies. A component or subassembly will simply be referred to as a “job” unless where further distinction is necessary. Therefore, a product is composed of multiple jobs. Each job may need additional processing before mating with other jobs. The basic assumption for the problem is that product tardiness is not allowed as is typical in just-in-time manufacturing. However, products can be completed early. When a product is completed early, an earliness penalty is incurred. The problem is to schedule a set of products with deadlines to minimize the total weighted earliness penalty. Each product has its own weighted earliness penalty and inventory holding cost. A job within a product may have its own required set of operations. Inventory holding cost may be incurred by a job after an operation is completed and the job has to wait. This cost may differ from stage to stage in the routing of the job. In this paper, the earliness penalty for a product is calculated based on the completion time of the final operation of the product while the inventory holding cost of a job is equivalent to the earliness penalty based on the particular operation completed. Scheduling decisions continue to play a very prominent role in assessing the effectiveness of a manufacturing enterprise. Among the many objectives that are pursued in making scheduling decisions, earliness and tardiness penalties continue to rank quite high because of their direct effect on manufacturing cost. As a result, the scheduling literature continues to enjoy a regular stream of proposed techniques for addressing the problem for various types of shops (Framinan and Leisten, in press; Mason et al., 2005; Ramachandra and Elmaghraby, in press; Schultz et al., 2004a and Schultz et al., 2004b; Sen et al., 2003; Yalaoui and Chu, 2002; Yeung et al., 2004). Research in the deterministic production assembly job shop has been less extensive than that of the basic job shop. One of the major reasons is that the assembly job shop contains precedence relations between jobs and between operations. It also deals with staging delay time, which is the time that a job has to wait for its other mating jobs. Based on the nature of the problem, the generation of an optimal schedule generally requires a large computational time. An assembly job shop is a special form of the job shop problem. In general, the job shop problem is computationally intensive to solve (Garey and Johnson, 1979). For this reason, most researchers dealing with job shop or the assembly job shop problem focus their efforts on developing efficient solution heuristics that generate near-optimal solutions at reasonable computational time (Garey and Johnson, 1979; Mckoy, 1995). The low volume of scheduling research with product assembly consideration notwithstanding, there is a growing volume of work that is jointly considering both scheduling and assembly operations (Hicks et al., 2002; Lagodimos et al., 2004; Sun et al., 2003; Yokoyama 2004; Yokoyama and Santos, 2005). Chen and Wilhelm (1993) presented a heuristic for kitting in a multi-echelon assembly shop. The objective was to allocate on-hand stock and future anticipated deliveries to kits in order to minimize total cost due to earliness, tardiness, and inventory. A heuristic for maximizing machine utilization in an assembly job shop subject to satisfying job deadlines was developed by Doctor et al. (1993). Their heuristic was based on the construction of non-delay schedules and was effective in solving problems involving products with no more than three assembly levels. Chen and Wilhelm (1994) developed an approach for minimizing the total cost of allocating resources in a multi-echelon assembly system. Their optimization method was based on Lagrangian relaxation. McKoy and Egbelu (1998) proposed a heuristic for minimizing makespan in a job shop. They also constructed a mathematical model for the problem and solved some problem instances to obtain optimal solutions. They developed a heuristic and tested it against an exact solution procedure. McKoy and Egbelu (1999) considered the problem of scheduling jobs with both processing and assembly requirements in an assembly job shop. The objective was to minimize the production makespan. A heuristic method was developed in the paper. The heuristic produced results that averaged 1.20% from the optimal. The objective of this paper is to develop a good heuristic for solving the assembly shop problem, where jobs possess both processing and assembly operations. In Section 2, the problem formulation is presented. Several optimality properties, which formed the basis for the heuristic, are presented in Section 3. Section 4 presents the heuristic. An example to illustrate the heuristic is given in Appendix B. Results and analysis are presented in Section 5. Section 6 is the conclusion. The proofs of some properties are given in the Appendix A.

This paper addressed the assembly job shop problem in which the objective is to minimize the weighted earliness penalty subject to no products being tardy. In the problem, machine idle time is allowed and there is no cost for a machine staying idle if such idle time improves the solution to a problem. The problem environment considered is typical of a JIT system widely used in manufacturing. Because of the computational time complexity function of the problem, a heuristic solution approach was adopted. The heuristic is an extension of the heuristic to the single machine problem to minimize the weighted earliness penalty (Pathumnakul, 2000). The solutions obtained from the new heuristic were compared to the optimal solutions for 50 test problems. The results indicate that the performance of the new heuristic is good.