bound algorithm
در نشریات گروه فنی و مهندسی-
در این مقاله مساله زمان بندی تک ماشین با فعالیت های روبه زوال خطی و فرض ورود غیرهم زمان کارها مورد بررسی قرار گرفته شده است که هدف حداقل کردن تعداد کارهای دارای دیرکرد می باشد. با تکیه بر ادبیات موضوع ثابت می گردد که مساله موردنظر یک مساله NP-hard است. درابتدا یک مدل ریاضی برای مساله ارایه شده و جهت حل مساله به صورت بهینه نیز یک الگوریتم شاخه وکران با درنظر گرفتن اصول غلبه و حدود پایین پیشنهاد گردیده است. به منظور بررسی عملکرد الگوریتم شاخه وکران پیشنهادی و همچنین تاثیر پارامترهای مرتبط روی این الگوریتم، نتایج محاسباتی در چهار مرحله ارایه شده است. براساس آزمون تحلیل واریانس مشخص گردید که کارایی الگوریتم شاخه وکران بالاست به طوری که قادر به حل اکثر مسایل با ابعاد 30 فعالیت در مدت زمان قابل قبولی بوده و متوسط درصد کل گره های قطع شده در تمامی مسایل حداقل برابر با 85.61 درصد می باشد. همچنین نشان داده شد که مسایل با لاندای بزرگ تر و نرخ زوال کوچک تر سخت هستند و متوسط زمان حل الگوریتم در آن ها بالا می باشد. ازطرفی اگر موعد تحویل کارها بزرگ یا کوچک باشند نیز مساله ساده بوده و زمان حل آن نسبت به مسایل با موعد تحویل متوسط کمتر است.
کلید واژگان: فعالیت های روبه زوال، زمان بندی، تعداد کارهای دارای دیرکرد، ورود غیرهم زمان، الگوریتم شاخه وکرانJournal of Industrial Engineering Research in Production Systems, Volume:9 Issue: 19, 2022, PP 169 -187In this paper, the single machine scheduling problem with linear deteriorating jobs under release times is considered where the objective is to minimize the number of tardy jobs. The problem is proved NP-hard according to the literature review. At first, a mathematical model is presented to the problem and a Branch and Bound algorithm with considering dominance rules and lower bounds is supposed to solve the problem optimally. Computational results are presented in four parts to evaluate the performance of the proposed algorithm and the effect of related parameters on the algorithm. According to the variance analysis test, it was found that the efficiency of the branch and bound algorithm is high so that it is able to solve the most problems with job size 30 within a reasonable time and the average percentage of entire fathomed nodes in all the problems is at least 85.61 percentage. It was also shown the problems with larger λ and smaller deterioration rates are difficult and the average solution time of the algorithm is high for them. On the other hand, if the due date of the jobs was big or small, the problem will be simple and the solution time is less than the problems with medium due dates.
Keywords: Deteriorating jobs, Scheduling, Number of Tardy Jobs, Release Time, Branch, bound algorithm -
Machine maintenance is performed in production to prevent machine failure in order to maintain production efficiency and reduce failure costs. Due to the importance of maintenance in production, it is necessary to consider an integrated schedule for production and maintenance. Most of the literature on machine scheduling assumes that machines are always available. However, this assumption is unrealistic in many industrial applications. Preventive maintenance (PM) is often performed in a production system to prevent premature machine failure in order to maintain production efficiency. However, this assumption is inappropriate in real industrial cases. Machine maintenance plan is often performed in a production system to prevent premature machine failure in order to maintain production efficiency. Parallel machine layout is very common in modern production systems. Its performance sometime has a key impact on overall productivity. In this paper, a parallel machine scheduling problem with individual maintenance operations is considered. Then, a mathematical model is formulated including scheduling and maintenance operation optimization. The objective is to assign all jobs to machines so that the completion time and the average cost are minimized, jointly. Maintenance is considered in time intervals. To solve the proposed problem, a branch and bound (B&B) algorithm is adapted and proposed. The results show the applicability of the mathematical model in production systems and efficiency of the adapted B&B in comparison with Gams optimization software.Keywords: Production scheduling, preventive maintenance, joint optimization, adapted branch, bound algorithm
-
زمان بندی هم زمان برای سیستم های تولید دومرحله ای شامل یک مرحله ی پردازش قطعات و یک مرحله ی مونتاژ، موجب تحقق اهداف ایده آل برای این سیستم ها می شود. در این مقاله برای اولین بار یک الگوریتم شاخه و کران جهت حل مساله زمان بندی در سیستم تولیدکارگاهی انعطاف پذیرهمراه با یک مرحله ی مونتاژ با هدف حداقل کردن زمان تکمیل محصولات ارایه شده است. باتوجه به زمان بر بودن روش های حل شاخه و کران، جهت افزایش کارایی الگوریتم پیشنهادی و کاهش زمان اجرای آن، دو کران پایین ارایه و دو استراتژی جست وجوی تحت عنوان جست وجوی اولین بهترین و جست وجوی عمق مورد بررسی قرار گرفت. هم چنین به منظور تعیین حد بالا برای هر شاخه، از الگوریتم جست وجوی همسایگی متغیر (VNS) استفاده شده است. به منظور درک بهتر مساله، یک مدل برنامه ریزی عدد صحیح مختلط (MIP) همراه با پارامترها و متغیرهای تصمیم مورد نیاز تشریح شده است. ازآن جایی که مساله مورد مطالعه از نوع مسایل رده ی سخت محسوب می شود، عملکرد الگوریتم های پیشنهادی در حل مساله با ابعاد کوچک مورد ارزیابی و مقایسه قرار گرفته است. نتایج ارزیابی نشان داد که استراتژی جست وجوی عمق عملکرد بهتری داشته و موجب افزایش کارایی الگوریتم شاخه و کران پیشنهادی و کاهش زمان حل می شود.
کلید واژگان: زمانبندی، تولیدکارگاهی انعطاف پذیر_ مونتاژ، الگوریتم شاخه و کرانJournal of Industrial Engineering Research in Production Systems, Volume:8 Issue: 17, 2021, PP 347 -359Concurrently scheduling for two-stage production systems consist of a processing stage and an assembly stage causes to achieve the ideal result for these systems. This paper aims to propose a branch and bound (B&B) algorithm for the scheduling problem in a flexible job shop followed by an assembly stage. The objective function is the total completion time of products (makespan). Due to time consuming the classic B&B algorithms in solving optimization problems, two efficient lower bounds are developed to reduce the run time. Moreover, two search strategies the so-called the Best First Search (BFS) and the Depth-First Search (DFS) are introduced to enhance performance of the proposed algorithm. The variable neighborhood search (VNS) is applied to determine proper upper bound for solution of the problem. To more clarification, the problem is modeled as a mixed-integer linear programming (MIP) model with definition need parameters and decision variables. Since the problem is well known as NP-hard strongly, performance of the proposed algorithm is investigated in comparison to the exact solutions provided by the mathematical model for the small-sized instances. The evaluation results showed that the depth search strategy has performed better than the other one. This search strategy has could to enhance efficiency of the proposed algorithm, and has significantly reduced the solution time.
Keywords: Scheduling, Flexible flow shop, Sssembly, Branch, bound algorithm -
This paper investigates steel-making continuous casting (SCC) scheduling problem. SCC is a high temperature and large-scale logistics machining process with batch production at the last stage that was identified as the key process of modern iron and steel enterprises. This paper presents a mathematical model for scheduling SCC process. The model is developed as a Mixed Zero- One Linear programming (MZOLP) based on actual production situations of SCC. The objective is to schedule a set of charges (jobs) to minimize the earliness and tardiness penalty costs as well as the charge waiting time cost. The solution methodology is developed based on a branch-and-bound algorithm. A heuristic method is presented at the beginning of the search in order to compute an initial upper bound. A lower bound and an upper bound are developed and a method for reducing branches is established based on the batch production in the continuous casting (CC) stage. Moreover, branching schemes are proposed. The branch- and- bound algorithm incorporating the initial upper bound, the lower and upper bound, the method for reducing branches, and branching schemes is tested on a set of instances. The analysis shows the efficiency of the proposed features for the algorithm.
Keywords: Steel making, continuous casting, Production Scheduling, Branch, Bound Algorithm -
Journal of Optimization in Industrial Engineering, Volume:12 Issue: 25, Winter and Spring 2019, PP 167 -172One of the most important decision making problems in many production systems is identification and determination of products and their quantities according to available resources. This problem is called product-mix. However, in the real-world situations, for existing constrained resources, many companies try to provide some products from external resources to achieve more profits. In this paper, an integrated product-mix-outsourcing problem (IPMO) is considered to answer how many products should be produced inside of the system or purchased from external resources. For this purpose, an algorithm based on Theory of Constraints (TOC) and Branch and Bound (B&B) algorithm is proposed. For investigation of the proposed algorithm, a numerical example is presented. The obtained results show the optimal result by the new algorithm is as same as the results of integer linear programming.Keywords: Product-mix, Outsourcing, Theory of constraints, Branch, bound algorithm
-
فرآیند تخلیه از کلیدی ترین فعالیت های همزمان با بحران هنگام رخداد فجایع است. در پژوهش های مدیریت بحران، فرض بر وجود مکان های اسکان اضطراری از پیش تعیین شده ای است که تخلیه افراد از نواحی بحران زده به سوی آن ها انجام می شود. ما در این مقاله در پی یافتن یک پایگاه اسکان از میان مجموعه پایگاه های پیش بینی شده هستیم که جریان تخلیه افراد از ناحیه بحران را بیشینه می کند و بنابراین امکان تصمیم گیری درباره مکان های امن را همزمان با وقوع بحران برای تصمیم گیرندگان فراهم می کند. این مسئله را به صورت دو مدل غیرخطی در حالت ایستا و پویا، و با رویکرد شبکه جریان مدل سازی می کنیم. علاوه بر این یک مدل استوار پویا برای مسئله تخلیه-مکان یابی توسعه داده ایم تا عدم قطعیت مربوط به ظرفیت مسیرها در هنگام رخداد بحران را نیز در نظر بگیریم. در این مقاله، برای نخستین بار متغیر تصمیم مکان یابی را در مدل بیشینه جریان وارد کرده ایم. سپس با استفاده از ساختار مدل ها دو کران بالا و دو الگوریتم بهینه برای حل آنها توسعه می دهیم. الگوریتم های بهینه را بر پایه ی ترکیب روش های موجود برای بیشینه سازی جریان شبکه با روش شاخه و کران توسعه داده ایم. عملکرد کران های بالا را با حل مسئله های تصادفی هم از نظر زمان حل و هم فاصله با حل بهینه می سنجیم. زمان اجرای الگوریتم های دقیق را نیز بر روی همین مسئله های تصادفی می آزماییم و نتیجه مقایسه را گزارش می نماییم. در پایان نیز، الگوریتم های پیشنهادی را برای داده های واقعی یک شبکه شهری به کار گرفته و نتایج آن را گزارش کرده ایم.کلید واژگان: لجستیک بحران، مسئله تخلیه، مکان یابی، مسئله شبکه جریان، شبکه جریان ایستا، شبکه جریان پویا، مدل استوار پویاEvacuating people to the safe zones is the most crucial operation in many disasters. We have presented mathematical models in this paper, to combine the locational decisions with the max-flow problem in order to select the safe destination that maximizes the number of dispatched people, both for the static and dynamic cases.
Existing frameworks for emergency logistics, address the evacuation process based on fixed and pre-determined destinations usually with a strategic perspective. The unpredictable and turbulent nature of a disaster may, however, disrupt the predictions.
Furthermore, the primary goal in emergency situations is to dispatch people from the danger zone to a safe place, no matter where. A non-linear integer programming model is developed in this paper for selecting one destination in a capacitated network. We have also formulated the robust counterpart of the dynamic model in order to contribute the uncertainty of the capacity of routes during a disaster.
The special structure of the model and its similarity to the max-flow problem let us develop exact algorithms and heuristics for the single destination location problem. The solution methods are based on combining a branch and bound approach with the existing algorithms for the max-flow problem.
Our proposed heuristics use the idea of adding a super-sink to the network to generate upper bounds very fast. The exact algorithms as well as the heuristics are tested on randomly generated instances as well as a real world network. The mean and variance of their computation times are reported. They are compared according to their performance (gap to optimality) and their behavior amongst different categories of the graphs. We have also used the real data for Mitte-center berlin to implement our algorithms for an existing data set. The results of the algorithms for this case are also reported in the results section.Keywords: Emergency Logistics, Network Theory, Evacuation-Location, Branch, Bound Algorithm -
سیستم تولید جریان کارگاهی مونتاژی شامل دو مرحله است. در مرحله اول پردازش قطعات صورت می گیرد و معمولا به صورت یک ایستگاه با ماشین های موازی درنظر گرفته می شود. مرحله دوم نیز یک ایستگاه یا خط مونتاژ می باشد که قطعات پردازش شده، در آن مونتاژ و محصولات نهایی کامل می شود. در این تحقیق فرض می شود قرار است تعدادی محصول از انواع مختلف تولید شود و هر محصول جهت کامل شدن، نیازمند قطعاتی مشخص است. بعضی از قطعات محصولات مشترک و مشابه بوده و بعضی قطعات هم مختص یک محصول می باشد لذا باتوجه به تولید قطعات مشابه، موضوع زمان آماده سازی (setup time) و تولید دسته ای قطعات مشابه نیز نیازمند بررسی است. هدف عبارتست از زمانبندی پردازش قطعات در ایستگاه اول و مونتاژ محصولات در ایستگاه دوم بطوری که زمان تکمیل کل محصولات حداقل شود. طبق بررسی پیشینه تحقیق، این مساله جزء مسائل NP-hard محسوب می گردد. ابتدا پارامترها و ویژگی های مساله تعریف و پس از ارائه مدل ریاضی مساله، یک الگوریتم شاخه و کران برای حل مساله مورد نظر در ابعاد کوچک و متوسط ارائه می شود. همچنین به منظور افزایش کارایی الگوریتم پیشنهادی، دو حد پایین و دو حد بالا برای جواب مسائل توسعه داده می شود. در نهایت، چندین مساله تست با شرایط متنوع طراحی و عملکرد الگوریتم پیشنهادی در حل این مسائل ارزیابی شده است.کلید واژگان: زمانبندی، جریان کارگاهی مونتاژی، الگوریتم شاخه و کران، زمان تکمیلAssembly flow shop production system includes two stages. In the first stage that is usually assumed one station with some parallel machines, the parts are processed. The second stage is an assembly station (or line) to assemble the parts and complete the products. Suppose that a number of products of different kinds are ordered to be produced and each product needs a set of several parts to complete. Some of the parts are common and some others are unique for each product. Therefore it is important to study the setup times and batch production. The aim is to schedule the parts for process and the products for assembly with the minimum complete time objective. Literature review shows that the considered problem is a NP-Hard problem, so the problem characteristics and its parameters are defined and then a branch and bound algorithm is introduced to solve the small and mediocre problems. Some lower bounds and upper bounds are improved to increase the algorithm efficiency. Finally, a variety of problem is designed and performance of the proposed algorithm is evaluated in solving this problems.Keywords: scheduling, Assembly flow shop. Branch, amp, Bound algorithm, Makespan
-
Nowadays, offering extended warranty is considered as a lucrative source of income from the perspective of the after-sale service providers. Meanwhile, the main concern is presence or absence of base warranty and strategies adopted by the manufacturer during this period. Moreover, extended warranty structure must be responsive and customer oriented, which not only control the services cost but also to handle the customers requirement in a timely manner. In this paper, an extended warranty distribution network is designed from the perspective of a third party (3P) for supporting multi-indenture products in conjunction with base warranty. The proposed network is two-echelon; in this regard, a depot repair center is considered as the first echelon and a number of operational repair centers are selected at the second echelon. In order to decrease the cost of maintenance and spare parts logistics, a novel imperfect preventive maintenance approach is established based on the concept of virtual age. The third party aims to determine the optimum level of spare parts for each component of products at each repair centers in a way that: (1) total expected backorders is minimized (2) total maintenance and retrieval costs of product components are controlled. For optimizing the proposed model, an exact hybrid solution approach regarding Branch-and-Bound algorithm and Variable Neighborhood Search is presented. The obtained results showed the presence of a base warranty on a product has more advantages for third parties even without preventive maintenance.Keywords: Extended warranty, Warranty distribution network, Imperfect preventive maintenance, Branch, Bound Algorithm, Variable neighborhood search algorithm, Monte-Carlo simulation
-
Transportation Discrete Network Design Problem (TDNDP) aims at choosing a subset of proposed projects to minimize the users total travel time with respect to budget constraint. Because TDNDP is a hard combinatorial problem, recent research has widely addressed heuristic approaches and ignored the exact solution. This paper is going to explore how application of parallel computation can affect the performance of an exact algorithm in TDNDP. First, we show that the Branch-and-Bound (B&B) algorithm proposed by LeBlanc is well adapted to a parallel design with synchronized Master-Slave (MS) paradigm. Then we develop a parallel B&B algorithm and implement it with two search strategies of Depth-First-Search (DFS) and Best-First-Search (BFS). Detailed results over up to 16 processing cores are reported and discussed in an illustrative example of the Chicago Sketch network. The results suggest an almost linear speedup for both strategies which slightly drops as more processing cores are added. When using 16 processing cores the speedup values of 11.80 and 12.20 are achieved for DFS and BFS strategies respectively. Furthermore, the BFS strategy reveals a very fast parallel performance by finding the optimal solution via the minimum computational effort.Keywords: Transportation discrete network design, Parallel Computing, Parallel branch, and, bound algorithm, Master, Slave Paradigm, Depth, First, Search, Best, First, Search
-
International Journal of Optimization in Civil Engineering, Volume:6 Issue: 2, Spring 2016, PP 187 -209Dynamic lot sizing problem is one of the significant problem in industrial units and it has been considered by many researchers. Considering the quantity discount in purchasing cost is one of the important and practical assumptions in the field of inventory control models and it has been less focused in terms of stochastic version of dynamic lot sizing problem. In this paper, stochastic dynamic lot sizing problem with considering the quantity discount is defined and formulated. Since the considered model is mixed integer non-linear programming, a piecewise linear approximation is also presented. In order to solve the mixed integer non-linear programming, a branch and bound algorithm are presented. Each node in the branch and bound algorithm is also MINLP which is solved based on dynamic programming framework. In each stage in this dynamic programming algorithm, there is a sub-problem which can be solved with lagrangian relaxation method. The numeric results found in this study indicate that the proposed algorithm solve the problem faster than the mathematical solution using the commercial software GAMS. Moreover, the proposed algorithm for the two discount levels are also compared with the approximate solution in mentioned software. The results indicate that our algorithm up to 12 periods not only can reach to the exact solution, it consumes less time in contrast to the approximate model.Keywords: dynamic lot sizing problem, total quantity discount, branch, bound algorithm, dynamic programming, lagrangian relaxation method
-
In the realm of scheduling problems, different sources of uncertainty such as probabilistic durations of jobs or stochastic breakdowns of machines can arise. Given this, one highly desirable characteristic of an intelligent schedule is to bring better punctuality with less efficiency-loss because a dominant factor in customer appreciation is punctuality. It is also one of the most intangible topics for managers when a due date is predetermined to deliver jobs. In this paper, we address the β-robust job shop scheduling problem when the processing time of each operation is a normal random variable. We intend to minimize the deviation of makespan from a common due date for all jobs which corresponds to maximizing the service level, defined as probability of the makespan not exceeding the given due date. We develop a branch-and-bound algorithm to solve the problem. Using a set of generated benchmark instances, the performance of the developed algorithm has been evaluated.Keywords: Job Shop, Stochastic scheduling, Branch, and, bound algorithm
-
Air defense is a crucial area for all naval combat systems. In this study, we consider a warship equipped with an air-defense weapon that targets incoming threats using surface-to-air missiles. We define the weapon scheduling problem as the optimal scheduling of a set of surface-to-air missiles of a warship to a set of attacking air threats. The optimal scheduling of the weapon results in an increase in the probability of successful targeting of all incoming threats. We develop a heuristic method to obtain a very fast and acceptable solution for the problem. In addition, a branch and bound algorithm is developed to find the optimal solution. In order to increase the efficiency of this algorithm, a lower bound, an upper bound and a set of dominance rules have been developed. Using randomly generated test problems, the performance of the proposed solution approaches is analyzed. The results indicate that in all practical situations, the branch-and-bound algorithm is able to solve the problem optimally in less than a second.Keywords: Weapon scheduling problem, naval combat systems, branch, bound algorithm
-
A One-Dimensional Binary Integer Programming Problem (1DB-IPP) is concerned with selecting a subset from a set of k items in budget constraint to optimize a goal function. In this problem a dominant solution is defined as a feasible selection to which no further item could be added in budget constraint. This paper presents a simple algorithm for Enumeration of Dominant Solutions (EDS) and investigates its functionality. The algorithm is then applied on the formulation of the Network Design Problem (NDP) with fixed travel-time links. The problem is a case study of 1DB-IPPs in the transportation planning literature which arises in the networks where the link travel-times are not sensitive to the amount of flow. The results are reported in detail for three illustrative examples and compared with the results of the Branch-and-Bound (B&B) algorithm. These examples suggest that in lower budget levels up to 40.2, 40.3 and 27.1 percentages the EDS algorithm outperforms the B&B algorithm. However, the overall performance of the B&B algorithm is notably faster in higher budget levels.Keywords: Enumeration, dominant solution, branch, and, bound algorithm, network design problem
-
موضوع مورد مطالعه در این نوشتار «زمان بندی اطاق های عمل» است که در آن انجام هر عمل جراحی به چهار مرحله تقسیم بندی شده که منابع اصلی مورد نیاز هر مرحله جراحان و اطاق های عمل هستند. این مسئله توسط یک مدل برنامه ریزی عدد صحیح مختلط فرموله شده که در آن تخصیص بیماران به اطاق های عمل و توالی عمل های بیماران هر اطاق طوری تعیین می شود که تابع هدف دومعیاره ی میزان اضافه کاری جراحان و فواصل بیکاری بین جراحی های آن ها کمینه شود. به منظور حل مسئله، یک الگوریتم شاخه و کران توسعه داده شده و با تولید نمونه مسائلی، کارایی الگوریتم بررسی شده و حساسیت برخی پارامترها مورد تحلیل قرار گرفته است.
براساس نتایج ارائه شده، بهتر است 20 درصد به طول کل زمان جراحی های هر جراح اضافه کرده و آن را به عنوان طول بازه کاری وی در نظر بگیریم زیرا بازه های کاری بزرگ تر هیچ گونه بهبود چشم گیری در جواب بهینه نخواهند داشت.
کلید واژگان: زمان بندی اطاق عمل، الگوریتم شاخه و کرانIn this research, the operating room scheduling problem is studied. During recent years, this problem has attracted many researchers in an eort to reduce costs and raise the quality of health services. In this article, a surgery is divided to four steps and the required resources for each step are determined, where surgeons and operating rooms are the main critical resources. For this problem, a mixed integer programming model is developed, in which, assignment of patients to rooms and, also, the sequence of patient surgery, are determined, such that the bi-objective function, including additional work costs and idle time costs of surgeons, is minimized. This model is able to solve very small size problems in a reasonable time. Thus, a branch-and-bound algorithm has been developed to nd an optimal solution, in each node of which, a patient is assigned to a room. The sequence of operations for patients of a room and also for patients of a surgeon is established using parent-child relations of the search tree. Moreover, in order to prevent the enumeration of repetitive nodes or the extension of nodes that surely will not improve the best found solution, four properties are developed. This algorithm has been implemented in C++ programming language and a set of test problems are generated to evaluate its eciency and analyze the sensitivity of some parameters. Based upon presented results, the solution time is increased if each of the three following parameters is increased: Number of patients, number of surgeons or average number of possible rooms for each patient. In addition, it seems that if 20% is added to the total surgery time of each surgeon, this new time interval is proper to be considered as the working time interval, and longer intervals will not noticeably improve the quality of the optimal solution. It is shown in this paper that 0.25 is the best suitable coecient for the idle gaps of surgeons in the objective function.Keywords: Operating room scheduling, branch, and, bound algorithm -
برنامه ریزی ظرفیت تولید و زمانبندی تولید جزئی از فرآیند تصمیم گیری در زنجیره تامین بسیاری از صنایع ساخت و خدماتی محسوب می شوند که نقش مهمی را در برآورده سازی نیازهای مشتریان و ارتقای سطح خدمت دهی به مشتریان ایفا می نمایند. از آنجائیکه این دو فرآیند در دو سطح متفاوت از زنجیره تامین عمل می نمایند (برنامه ریزی ظرفیت در سطح تاکتیکی و زمانبندی تولید در سطح عملیاتی)، لذا معمولا تصمیمات مربوط به این دو حیطه نیز مستقلا و جدای از هم اتخاذ می شود. در چنین شرائطی شدنی بودن تخصیص ظرفیت انجام شده در سطح تاکتیکی، زمانیکه برنامه بصورت عملیاتی وارد کارگاه می شود، به عنوان یکی از چالش های اصلی این رویکرد تصمیم گیری مجزا، مطرح است. لذا در این تحقیق، پس از مدلسازی یکپارچه مساله برنامه ریزی ظرفیت تولید و مساله زمانبندی تولید دو ماشینه، به ارائه یک رویکرد حل تحلیلی مبتنی بر تجزیه مساله پرداخته شده است. در راستای کمینه سازی حداکثر زمان تکمیل سفارشات، مفهومی تحت عنوان «زوج سفارش» تعریف، و الگوریتمی جهت تعیین زوج سفارشات بهینه بر مبنای مساله تخصیص متقارن ارائه می شود. سپس در راستای تعیین توالی بهینه ی زوج سفارشات، الگوریتم شاخه و کرانی بر مبنای سه کران پائین پیشنهادی و همچنین دو استراتژی جستجوی عمق اول و سطح اول، طراحی و در راستای افزایش کارآیی آن تعدادی ویژگی ریاضی اثبات، و بر اساس آن ها تعدادی قائده چیرگی جهت مساله استخراج شده است. همچنین جهت تعیین مقادیر تخصیص ظرفیت به عملیات، یک الگوریتم جستجوی همسایگی طراحی و بر اساس ویژگی های ساختاری مساله بهبود داده شد.
کلید واژگان: برنامه ریزی ظرفیت، زمانبندی سفارشات، الگوریتم شاخه و کران، کران پائین، استراتژی جستجوInternational Journal of Industrial Engineering & Production Management, Volume:24 Issue: 2, 2013, PP 117 -139Production capacity planning and scheduling are parts of decision process in supply chain of many manufacturing and service industries, which have important role in satisfying customer requirements and enhancing customer service level. Since these two processes performs in two different levels of supply chain (capacity planning in tactical level and scheduling in operational one), usually their decision are made independently. In such circumstances, the feasibility of capacity decisions in tactical level, when plan imports into the shop floor, is one of the critical challenges in this decision making approach. Hence in this paper, after formulating the capacity planning and two-machine scheduling problems integrately, an analytical solution approach will be presented. In order to minimize the maximum completion time of orders, concept of order pairs is defined and the optimal orders pairs are established based on the optimal solution of symmetric assignment problem. Afterwards, to determine the optimal sequence of order pairs, a branch and bound procedure is designed which is based on three proposed lower bounds, depth first and best first strategies. To improve the efficiency of algorithm, some mathematical properties are proved and some corresponding dominance rules are derived. Furthermore, to delineate the quantity of resource allocation to the operations, a neighborhood search algorithm is designed and improved based on some structural properties of problem.
Keywords: Capacity Planning, Order Scheduling, Branch, Bound Algorithm, Lower Bound, Search Strategy -
در این مقاله مسئله زمان بندی فلوشاپ دو ماشین با در نظر گرفتن ورود غیر همزمان و با هدف کمینه سازی تعداد کارهای دیرکرددار بررسی شده است. در ابتدا پیچیدگی مساله بررسی و ثابت شده که مساله NP hard است. بنابراین برای حل مسئله فوق یک الگوریتم ابتکاری که قابلیت حل مسائل با ابعاد خیلی بزرگ را دارد، ارائه شده است. همچنین به منظور حل بهینه مسئله از روش شاخه و کران با در نظر گرفتن الگوریتم ابتکاری به عنوان حد بالا بهره گرفته شده است. نتایج محاسباتی نشان می دهد که رویه شاخه و کران مسائل با ابعاد 28 فعالیت در گروه High و 20 فعالیت در گروه Low را در زمان منطقی و به طور کامل حل می کند، که این امر کارآیی حد بالا، حدود پایین و اصول غلبه ارائه شده برای مسئله را نشان می دهد. همچنین نشان داده شد که متوسط نسبت جواب بهینه به الگوریتم ابتکاری با هدف ∑(1-Ui) حداکثر 11/ 1 برابر می باشد که در مقایسه با الگوریتم های ارائه شده در تحقیقات مرتبط با کارهای دیرکرددار نسبت کوچکی می باشد. این نسبت نشان دهنده کارایی بالای الگوریتم ابتکاری است. با توجه به کارآیی بالای الگوریتم ابتکاری، مسائل نمونه با ابعاد بزرگ نیز حل و نتایج آن ارائه شده است.
کلید واژگان: فلوشاپ دو ماشین، تعداد کارهای دیرکرددار، ورود غیر همزمان، الگوریتم شاخه و کران، الگوریتم ابتکاریInternational Journal of Industrial Engineering & Production Management, Volume:23 Issue: 4, 2013, PP 389 -400In this paper, minimizing the number of tardy jobs in two-machine flowshop scheduling with non-simultaneous job entrance is discussed. It is proven that the complexity of the problem is NP_hard. Therefore, a heuristic algorithm is proposed to solve the large scale problems. Besides, an exact branch and bound algorithm with utilizing heuristic algorithm as upper bound proposed to achieve optimal solution. Computational results demonstrate that branch and bound method solves problems with 28 jobs in the set High and 20 jobs in the set Low in a reasonable time. Results show the capability of the proposed upper bound, lower bounds and dominance rules. Also, it is shown that the average ratio of optimal solution to the heuristic one with the objective ∑(1-Ui) is at most 1.11 which is smaller in contrast with other researches in the literature. This ratio proves efficacy of the proposed heuristic algorithm. Finally, according to efficiency of the presented approach, sample problems with large dimensions were solved and their results were displayed.Keywords: Two machine flowshop, number of tardy, non, simultaneous job entrance, Branch, Bound Algorithm, Heuristic Algorithm
- نتایج بر اساس تاریخ انتشار مرتب شدهاند.
- کلیدواژه مورد نظر شما تنها در فیلد کلیدواژگان مقالات جستجو شدهاست. به منظور حذف نتایج غیر مرتبط، جستجو تنها در مقالات مجلاتی انجام شده که با مجله ماخذ هم موضوع هستند.
- در صورتی که میخواهید جستجو را در همه موضوعات و با شرایط دیگر تکرار کنید به صفحه جستجوی پیشرفته مجلات مراجعه کنید.