ترمیم برنامه مبتنی بر محدودیت برای پروژه های توسعه محصول با محدودیت های زمان محدود

In today's changing marketplace, accurate project planning and scheduling for product development becomes difficult. It is important for an R&D organization to quickly recognize the impact of unexpected events and rapidly reschedule product development projects. In addition, it has become more important for a firm to meet the due date requirement for a product development project than to satisfy the available resource capacity, since a late project will incur a great sales loss or a large amount of penalty to customers. This paper models the scheduling of product development projects as a dynamic constraint satisfaction problem, where the due date constraint is considered as a “hard” constraint that cannot be violated. All unexpected changes during the product development are regarded as additions or deletions of constraints to the problem. A reactive scheduling methodology based on the meta-heuristic approaches is developed to repair a disrupted schedule with the minimum cost of resource conflicts. The proposed approaches have been tested on several benchmark problems and satisfactory results have been obtained.

Product development is the competitive advantage for many industries. To maintain market shares, industries need to effectively manage their product development projects and bring their products to market as early as possible. In today's changing marketplace, accurate project planning and scheduling for product development becomes difficult. Unexpected events (e.g., engineering changes, delays of certain activities, etc.) frequently occur during the product development. It is important for an R&D organization to quickly recognize the impact of unexpected events and effectively reschedule the affected project activities. Moreover, in today's globalized and highly competitive market, it has become more important for a firm to meet the due date requirement for a product development project than to satisfy the available resource capacity, since a late project will incur a great sales loss and a large amount of penalty to customers. Especially for a development project contracted from a world-class company, a small firm usually does not have enough power for bargaining the project due date. However, the unavailable resource capacity can be resolved by working overtime, outsourcing, sharing resources with other projects, hiring more manpower or purchasing additional equipment. In this situation, it is important to have a scheduling decision making tool to assist project managers in repairing the disrupted project schedule with the “hard” due date constraint. Scheduling of a product development project can be viewed as a resource-constrained project scheduling problem (RCPSP), which has been investigated extensively in the literature (Özdamar and Ulusoy, 1995; Kolisch and Padman, 1997; Brucker et al., 1999). Since the resource-constrained project scheduling problem is NP-complete, optimization approaches are not suitable to solve practical-size problems. Therefore, heuristic approaches have been developed to construct a schedule effectively for practical use. In addition, in recent years, several studies have proposed the meta-heuristic approaches (Glover, 1986) for solving the RCPSP (Lee and Kim, 1996; Mori and Tseng, 1997; Cheng and Gen, 1998; Özdamar, 1999). Most of the research in RCPSP is concentrated on constructive methods to find an optimal or satisfactory schedule. Although extensive research has been done on the rescheduling problem in the manufacturing domain (Smith et al., 1990; Abumaizar and Svestka, 1997), little research has been performed on the dynamic aspect of RCPSP (Sathi et al., 1986; Zweben et al., 1993; Yan et al., 2002). There has been little research focus on scheduling of the product development project. With the advent of concurrent engineering (Winner et al., 1988), and Belhe and Kusiak (1995) developed a dynamic scheduling heuristic to minimize weighted lateness of design projects. Luh et al. (1999) developed a stochastic programming approach to schedule the design projects with uncertain number of iterations with the goal to minimize project tardiness. Hapke and Slowinski 1994 and Hapke and Slowinski 1996 represented uncertain activity duration by fuzzy sets and applied dispatching rules to determine the schedules with the minimum fuzzy makespan for software development projects. Wang 2002 and Wang 2004 developed fuzzy project scheduling approaches for product development projects with uncertain activity duration and the preferred due date constraint to minimize the possibility of the project being late. This research models the scheduling of the product development projects as a dynamic constraint satisfaction problem (Dechter and Dechter, 1988), where the project due date is considered as a “hard” constraint that cannot be violated. All unexpected changes during the product development are considered as additions or deletions of constraints to the problem that may lead to constraint violations for the current schedule. This paper proposes meta-heuristic approaches including simulated annealing (Eglese, 1990) and genetic algorithms (Goldberg, 1989) to repair the disrupted schedule with the minimum cost of resource constraint violation. This will enable an R&D organization to recognize the impacts of unexpected events quickly and to reallocate the scarce resources among project activities efficiently. The paper is organized as follows. Section 2 formulates the reactive project scheduling problem as a dynamic constraint satisfaction problem. The meta-heuristic approaches for scheduling repair are presented in Section 3. The computational experiments are performed in Section 4. Finally, Section 5 concludes this paper.

This paper considered the scheduling of product development projects as a dynamic CSP and developed a reactive scheduling methodology based on meta-heuristics to repair a disrupted project schedule to cope with the unexpected events in uncertain product development. We found that the SA and GA approaches could be easily adapted for solving the reactive scheduling problem. The proposed SA and GA approaches were tested on several benchmark problems and satisfactory results were obtained. The proposed methodology investigates the dynamic aspect of product development that is the usual instance in practice to allow an R&D organization to quickly recognize the impact of unexpected events and quickly reschedule the projects effectively. This agility allows the enterprise to take advantage of opportunities and to develop a product with less incurred time and cost. In the future research, we will improve the current proposed meta-heuristic approach for multiple projects environment and conduct a careful empirical study of how well the developed methodology matches reality.