یک روش جدید برای تولید کارگاهی مشکل برنامه ریزی همراه با محدودیت موعد مقرر با در نظر گرفتن داده های فرعی عملیات

We consider a kind of job shop scheduling problems with due-date constraints, where temporal relaxation of machine capacity constraint is possible through subcontracts. In practice, this kind of problem is frequently found in manufacturing industries where outsourcing of manufacturing operation is possible through subcontract. We present a heuristic algorithm that addresses the problem by solving a series of smaller subproblems to optimality. For the sake of efficiency, the algorithm repeatedly executes in two steps—(1) improving the sequence of operations and (2) picking out the operations to be subcontracted—on bottleneck machines. Experiments are conducted for example problems, and the result of the experiment confirms the viability of the suggested algorithm.

This study deals with a job shop scheduling problem with due dates. This type of problem has been the target of many studies for the past several decades (Baker, 1974; Brah, 1996; Ovacik and Uzsoy, 1997; Singer and Pinedo, 1998) and commonly used goals of these studies are the minimization of maximum lateness (Lmax) or the minimization of total tardiness. Numerous studies on the problem reflect the importance of the subject, but only a few of them ( Holloway and Nelson, 1974; Loerch and Muckstadt, 1994; Akkan, 1996) considered the problem from the perspective of temporal capacity adjustments like overtime and subcontracting. Timely and reliable delivery is becoming a more important factor for manufacturing companies since customer satisfaction becomes the paradigm of world class manufacturers (Wiendahl, 1995). In some industries, keeping due dates is the bottom line for survival. For example, the due dates of printing orders for periodical magazines in a competitive market are not negotiable (Lee et al., 1997). Also, the timing of the production of molds or dyes for new product initiation in a competitive market is also not negotiable (Yoon and Choi 1997). When timely delivery is a critical factor and subcontracting is possible at reasonable cost, keeping due dates is a very attractive option than breaking delivery promises. This study was motivated when the authors were involved with two manufacturing resource planning (MRP) projects for a very large printing company and a dye manufacturing company. For these two cases, there were many competent small companies that would do subcontract work any time upon request. From the other perspective, we expect that this kind of environment will dominate the manufacturing industries in the future with the emergence of Holonic manufacturing systems. In other words, with enough information and advance planning, we may have many competent subcontractors available in the future. Incidentally, the estimation of possible delivery dates in response to customer's inquiry is a very important task, but it is almost as difficult to optimize. It is so because we do not have enough time to consider all the detailed information about production plans and capacities at order contracting stages and furthermore, even the best elaborate plan is sure to be changed. These uncertainties are well demonstrated in the widely used hierarchical production management framework such as MRP (Akkan, 1996; Vollmann et al., 1997). For the products that are engineered to order, there are additional inherent uncertainties relating to design processes. Consequently the planned load often exceeds the normal production capacity, and manufacturers have no other way but to resort to subcontracting or overtime work to supplement the insufficient capacity (McLeavey and Narasimhan, 1985; Wiendahl, 1995). There have been several scheduling studies considering subcontracting or overtime. The study conducted by Holloway and Nelson (1973) is a pioneering study on the problem. They suggested an alternative formulation of job shop scheduling problem based on the concept that constraints on capacity and/or operation precedence relations may be circumvented if keeping due dates is more important. Although they did not specifically mention the decision problems relating to subcontracting and overtime, their research motivated many later studies. It seems like overtime scheduling has been the target of more studies compared to subcontracting. For a single machine problem, Gelders and Kleindorfer (1975) presented a branch-and-bound algorithm considering the trade-off between overtime and deferral costs. Even though their study was restricted to a single machine problem, they raised and considered several issues including machine availability constraints. More recently, Akkan (1996) presented an algorithm to plan overtime work for minimum costs in a job shop environment. Because his algorithm is a kind of order based scheduling methods and excludes the hierarchical production management framework, the algorithm cannot be applied to general manufacturing environments. However, he showed that the sequence of operations could be modified to minimize costs by scheduling overtime work. In contrast, Loerch and Muckstadt (1994) suggested a branch-and-bound algorithm for planning overtime in cyclic scheduling environment. Different from other studies, their formulation encompassed not only the overtime issues but also subcontract issues. Unfortunately though, their work did not include a solution method for subcontract problems. Their work contributed in arousing recognition to the important role of subcontracting in scheduling problems. Explicitly considering the subcontracting, Yoon and Choi (1996) suggested a simple algorithm based on a priority rule for scheduling problems. In their work, an operation is tentatively chosen to be subcontracted when its next operation cannot be finished within the latest finish time during the forward scheduling process. Though their algorithm is easy to implement, the quality of their solution is not very good owing to its myopic nature. In this paper, we propose an algorithm for planning subcontract operations in a job shop environment. Viewing that the overloads are the results of insufficient capacities and poor scheduling decisions, the algorithm is designed to effectively decrease tardiness measures by rescheduling or subcontracting the operations on bottleneck machines. In brief, the algorithm is composed of 2 phases. In the first phase, the sequence of operations on a bottleneck machine is repeatedly improved by Carlier algorithm (Carlier, 1982). In the second phase, a branch-and-bound algorithm picks out the operations to be subcontracted on a bottleneck machine. The algorithm is repeatedly executed together with the re-sequencing algorithm. Because the two phases are designed in an integrative manner, it is expected to obtain good solutions in a reasonable computation time. The rest of the paper is organized as follows. Section 2 defines the problem to be studied. Section 3 describes the suggested algorithm and introduces an interactive scheduling system. Section 4 analyzes the computational results. In Section 5, the conclusions of this study are drawn.

In this paper, we present a heuristic algorithm for a kind of job shop scheduling problem where each job has its due date and subcontracting of operations is allowed to keep due dates. This kind of problem demands more attention from the academia because it has not been studied extensively in spite of its significance in real manufacturing companies as well as its future implications for the coming era of Holonic manufacturing. We designed an algorithm with an idea that the tardiness can effectively be decreased by mitigating the overloads of the bottleneck machines that result from insufficient production capacities and poor scheduling decisions. Reflecting the idea and the characteristics of the problem, the algorithm concentrates on how to treat the operations on a bottleneck machine. Perceiving that planning of operations subcontracted and job shop scheduling are deeply related, the overall algorithm is designed to repeat re-sequencing and picking of subcontracting operations. Because the proposed algorithm addresses the problem by solving a series of smaller problems to optimality, it was expected to get good solutions in reasonable time. The expectation is verified by experiments that the suggested algorithm is shown to outperform other algorithms. In the area of planning and scheduling, there are many important decision processes still carried out by human planners with mere computer supports. Subcontracting is one of production capacity adjusting methods, and there are many kinds of load alignment methods (Wiendahl, 1995) that are not formalized yet. Accordingly, further studies that deal with these individual issues are required, and ultimately, integrating these individual studies may need to be investigated. Together with developing good algorithms, it is also required to design systems that are not only efficient but also easy to use for industrial practitioners.