برنامه ریزی ماشین آلات تک برای به حداقل رساندن تاخیر مجازات توسط روش فرا هیوریستیک
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|8042||2003||17 صفحه PDF||سفارش دهید||7450 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Industrial Engineering, Volume 44, Issue 2, February 2003, Pages 307–323
We consider the problem of scheduling a number of jobs on a single machine against a restrictive common due date. The paper consists of two parts: firstly a new and appropriate problem representation is developed. As the restrictive common due date problem is known to be intractable we decided, secondly, to apply meta-heuristics, namely evolutionary strategies, simulated annealing and threshold accepting. We demonstrate that our application of these meta-heuristics is efficient in obtaining near-optimal solutions by solving 140 benchmark problems with up to 1000 jobs. Furthermore, we compare their solution quality and find that a new variant of threshold accepting is superior to the other approaches.
Scheduling against due dates has been receiving considerable attention in the literature. One reason for this phenomenon is the growing pressure of competition on the international markets: firms have to offer a great variety of different and individual products while customers expect ordered goods to be delivered on time. To meet these kinds of requirements, principles and philosophies like Lean Management, Simultaneous Engineering, Just-in-Time-Production, etc. have been developed. For example, the Just-in-Time-Principle states that the right amount of goods should be produced or delivered at exactly the right time. Thus jobs are expected to be punctual, since late as well as early delivery is seen negatively. In a Just-in-Time-Production environment due dates can occur as common due dates if, for example, a set of jobs is needed simultaneously for an assembly at a higher stage of production. Furthermore, from a practical point of view, common due date problems are relevant in many applications: for instance, if a customer orders a bundle of goods which has to be delivered at a specified time, if a firm has installed a weekly bulk delivery to the wholesaler or if in a chemical or physical mixture some ingredients have a short half-life period. One of the pioneers studying common due date problems has been Kanet (1981). He considered the problem of minimizing the sum of deviations from a common due date and presented a polynomially bounded matching algorithm which solves the problem in View the MathML source time. This contribution has been extended in many directions; see, for example, Biskup and Cheng, 1999, Hall and Posner, 1991, Hoogeveen and van de Velde, 1991 and Panwalkar et al., 1982. An excellent review is given by Baker and Scudder (1990). When scheduling against a common due date some of the jobs may be completed early, that is, prior to the due date, while others are finished late. In both cases costs are incurred: early jobs cause holding costs by tying up capital while the effects of tardy jobs are dissatisfied customers and, in the long run, the loss of goodwill and reputation. Note that quantifying the incurred costs exactly is difficult, as most of them are not directly linked to cash flows. However, taking these kinds of costs into account is important in view of opportunity cost arguments. In the field of common due date scheduling two kinds of due dates, namely, restrictive and unrestrictive ones, are distinguished: a common due date is called unrestrictive if its optimal value has to be determined or if it is given and has no influence on the optimal sequence. Note that a given due date which is greater than or equal to the sum of processing times of all jobs is always unrestrictive. If, on the other hand, a common due date is given and may influence the optimal sequence of the jobs, it is called restrictive; thus a search for an optimal sequence has to be carried out with respect to the due date. Scheduling on a single machine is a special case of the multiple-machine environment. There are a number of reasons for focusing on single-machine problems: multiple-machine scheduling problems are as a rule computationally intractable and a better understanding of them and their inherent structure may be gained by analyzing single-machine problems. Furthermore, in many real life situations it is one machine that causes a bottleneck of the whole production environment, so that production planning should be orientated towards this single machine. In this paper we concentrate solely on single-machine problems. Furthermore, we assume that a restrictive common due date exists and for each of the jobs individual earliness and tardiness completion time penalties are given. The goal is to find a schedule, which minimizes the sum of earliness and tardiness costs. This problem is NP-hard (Hall et al., 1991 and Hoogeveen and van de Velde, 1991). Although the exact classification is an open question, no pseudopolynomial algorithm is known and it is conjectured that the problem is NP-hard in the strong sense (Lee, Danusaputro, & Lin, 1991). Consequently it has been tackled by meta-heuristic approaches, namely, tabu search (James, 1997) and parallel genetic algorithms (Lee & Kim, 1995). As both approaches are marred by an underlying weakness, which will be discussed in connection with the properties of the problems, we develop a new and appropriate problem representation, which overcomes this weakness. In this paper three meta-heuristics, evolutionary search (ES), simulated annealing (SA) and threshold accepting (TA) using a new problem representation are presented. In addition, a new variant of TA, namely ‘TA with a back step’, is introduced. The approaches are implemented and tested extensively on benchmark problems recently given by James, 1997 and Biskup and Feldmann, 2001. The remainder of the paper is structured as follows: in Section 2 the notation needed is introduced and the problem under study is formulated. Furthermore, some properties of this problem, which are used for the development of the new problem representation in Section 3, are stated. A simple heuristic to obtain feasible starting solutions and the meta-heuristic approaches are presented in Section 4. The choice of parameters can be found in Section 5. Computational results are summarized in Section 6 and the paper concludes with some final remarks.
نتیجه گیری انگلیسی
In the present paper we propose a new problem representation for the restricted common due date problem. As this problem is NP-hard the implementation of optimizing algorithms does not seem to be promising. Thus we decided to tackle the problem with meta-heuristics using the new problem representation. We solved 140 benchmark problems and compared the results to the best solutions known. It emerged that the objective function values of the benchmark problems have been improved by 5% on average. Furthermore, by comparing the performance of the heuristics it became apparent that a new variant of threshold accepting is very efficient in obtaining near optimal solutions. Ongoing research considers the problem of scheduling a number of jobs around a common due window instead of a common due date. Again, some important properties of optimal solutions exist (Yeung, Oguz, & Cheng, 2001) that might be useful to find an appropriate problem representation and to construct powerful heuristics.