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

An effective job shop scheduling (JSS) in the manufacturing industry is helpful to meet the production demand and reduce the production cost, and to improve the ability to compete in the ever increasing volatile market demanding multiple products. In this paper, a universal mathematical model of the JSS problem for apparel assembly process is constructed. The objective of this model is to minimize the total penalties of earliness and tardiness by deciding when to start each order’s production and how to assign the operations to machines (operators). A genetic optimization process is then presented to solve this model, in which a new chromosome representation, a heuristic initialization process and modified crossover and mutation operators are proposed. Three experiments using industrial data are illustrated to evaluate the performance of the proposed method. The experimental results demonstrate the effectiveness of the proposed algorithm to solve the JSS problem in a mixed- and multi-product assembly environment.

This paper develops a universal mathematical model of the JSS problem for the PBS and UPS of the apparel assembly process. A means is then demonstrated to improve the effectiveness of JSS in industries requiring the scheduling of both mixed- and multi-product, utilizing the job shop operations of PBS and UPS in the apparel industry where the production scheduling and resource allocation problems are optimized in terms of a genetic optimization process. In the proposed process, a novel representation is proposed which is particularly useful to those JSS problems involving not only the processing of multiple operations on one machine but also the processing of one operation on multiple machines. On the basis of this representation, a heuristic initialization process, modified crossover and mutation operator are developed. Some production tasks from real-world PBS and UPS are effectively scheduled by the proposed method. The scheduling objective addressed in this paper will help apparel enterprises to meet due dates and decrease inventories by optimizing the use of limited resources. Our future research will focus on the effects of various uncertainties on JSS, including unpredictable customer orders, machine breakdown, shortage of materials, and absence of operators, etc.

Today’s enterprises are confronted with ever increasing global competition and unpredictable demand fluctuations. These pressures compel enterprises to continuously improve the performance of their production processes in order to deliver the finished product within the most approximate period of time and at the lowest production cost. The apparel industry is one which is necessary to operate their assembly systems using mixed- and multi-product scheduling method due to rapid market changes. Job shop scheduling (JSS) for apparel production is a flexible multi-machine and multi-operation scheduling. At present, it is conducted by the shop-floor supervisor, and the effectiveness depends mainly on the supervisor’s experience, knowledge and prediction of the job shop’s performance. Their skills and experience are limited and thus the solutions are often not optimal and inconsistent even under similar situation. Establishing an optimization method to solve the JSS problem effectively is significant to the apparel industry in particular and other manufacturing industries requiring similar assembly operations at large. The JSS problem involves an assignment of a set of tasks to the workstations (machines) in a predefined sequence, while optimizing one or more objectives without violating restrictions imposed on the job shop. The history of the JSS problem can be traced back to more than 40 years ago (Manne, 1960 and Wagner, 1959). Since then an huge number of papers have been published (Agarwal et al., 2006, Cheng et al., 1996, Gordon et al., 2002 and Lauff and Werner, 2004). Some researchers have formulated various JSS models based on different production situations and problem assumptions. Manne (1960) formulated a simple integer programming JSS model. Liao and You (1992) extended Manne’s work to formulate a general n-job, m-machine JSS problem. Dessouky and Leachman (1997) developed two integer programming formulations which can easily handle high-volume manufacturing such as multiple machines of the same type, demand size greater than one unit for a particular product type and repeat visits to the same machine type. Recently, Gomes, Barbosa-Povoa, and Novais (2005) presented an integer linear programming model to schedule flexible job shops, which considered job re-circulation and parallel homogeneous machines. In this model, each product type has a pre-defined processing route. But in some industries such as apparel industry, each product type could have many alternative processing routes and how to select the optimal route is a very difficult task. Just-in-time production is adopted extensively in today’s manufacturing industry such as apparel industry to meet the production demand. In a just-in-time production environment, both earliness and tardiness (E/T) should be discouraged since completing jobs earlier than their due dates increases storage costs (earliness penalty costs) and completing jobs later than their due dates leads to customers’ dissatisfaction and loss of business integrity (tardiness penalty costs). In recent years, the scheduling objective considering E/T penalty costs has attracted more extensive attention. Some review articles have been published (Baker and Scudder, 1990, Gordon et al., 2002 and Lauff and Werner, 2004). Most of these studies focused on either single machine problems (Baker and Scudder, 1990, Seo et al., 2005 and Verma and Dessouky, 1998) or parallel machine problems (Tahar et al., 2006 and Ventura and Kim, 2003), and few discussed multi-machine JSS problem with different or similar due dates. A great number of algorithms have been developed to solve the JSS problem. Panwalkar and Iskander (1977) presented a survey of more than 100 heuristic rules (scheduling rules) for the JSS problem. But there is no guarantee of optimality in using these rules. Some classical optimization techniques have also been presented and can provide optimal or near optimal solutions, for example, branch and bound method (Brucker, Jurisch, & Sievers, 1994), dynamic programming method (Gelinas & Soumis, 1997), integer programming method (Graves & Lamar, 1983). It is well known that even very simple versions of the JSS problem are NP-hard (Hart, Ross, & Corne, 2005) and belong to the most intractable problems. So it is very difficult for these classical techniques to solve the large-scale JSS problem. In recent years, various intelligent algorithms have been studied and applied extensively, such as, tabu search method (Armentano and Scrich, 2000, Barnes and Chambers, 1995 and Liu et al., 2005), simulated annealing method (Diaz-Santillan and Malave, 2004, Ponnambalam et al., 1999 and Vanlaarhoven et al., 1992), neural network algorithm (Agarwal et al., 2006 and Jain and Meeran, 1998), ant colony algorithm (Boryczka, 2004, Holthaus and Rajendran, 2005 and Ying and Liao, 2003), and genetic algorithm (GA) (Cheng et al., 1996, Liu et al., 2006, Park et al., 2003 and Watanabe et al., 2005) in which GA is the most commonly used one and has been proven to be very powerful and efficient in finding heuristic solutions from a wide variety of applications (Chaudhry & Luo, 2005). Several studies about production scheduling in the apparel industry have been published. Bowers, Agarwal, and Knoxville (1993) proposed a 3-tiered hierarchical production planning and scheduling model to formally link long-term, short-term, and daily planning tasks. Tomastik, Luh, and Liu (1996) developed a low-order integer programming model using the Lagrangian relaxation method which integrated scheduling and resource allocation for a flexible manufacturing system. Chan, Hui, Yeung, and Ng (1997) used a GA to solve an assembly line balancing problem in the apparel industry and concluded that the GA was an appropriate tool to solve the dynamic and complex production scheduling problem. Wong, Mok, and Leung (2005) also developed a GA to balance an apparel assembly line of UPS and investigated the impact of different level of skill inventory on the assembly makespan. However, the above research focused on solving a particular problem using a specific method in a well-defined environment with various constraints, the universal mathematical model for the JSS problem in the apparel industry has not been presented and the JSS problem with E/T penalty objective has also not been investigated. Furthermore, most of the JSS problems in the apparel industry belong to the mixed- and multi-product scheduling problem. In a mixed-product scheduling problem, two or more production orders are produced in any intermixed sequence (Fig. 1(a)), whereas two or more products are processed separately in batches in a multi-product scheduling problem (Fig. 1(b)). However, the GA for the JSS problem in a mixed- and multi-product apparel assembly environment has not been developed so far. Full-size image (16 K) Fig. 1. Apparel assembly system. Each type of geometric shapes represents a production order. Figure options One of the main purposes of this paper is to construct a universal mathematical model for the JSS problem in progressive bundle system (PBS) and unit production system (UPS), which are the dominant forms of assembly in the apparel industry. The objective of this model is to minimize the total E/T penalties by deciding each order’s appropriate production starting time and operation assignment. In order to solve this mixed- and multi-product scheduling problem, a genetic optimization process based on GA will be developed, which includes a novel representation, a heuristic initialization process and modified crossover and mutation operators. The algorithm will then be used to solve the real-world JSS problems using data from real-life PBS and UPS, respectively. The rest of this paper is organized as follows: the mathematical model of the JSS problem is described in Section 2. In Section 3, a GA approach is then developed to solve this problem in detail. In Section 4, some experimental results, based on UPS or PBS, are presented. Finally, this paper is summarized and the further research is suggested in Section 5.