دانلود رایگان ترجمه مقاله زمانبندی زمان واقعی برای فروشگاه های جریان ترکیبی چند ورودی – الزویر 2011

مقاله انگلیسی رایگان

ترجمه فارسی رایگان 

فهرست مقاله:

چکیده
1. مقدمه
2. مکانیزم زمانبندی زمان واقعی مبتنی بر درخت تصمیم
2.1 چارچوب
2. 2. اجزاء
2.2.1 کنترل کننده زمان واقعی
2. 2. 2. زمان بند
2.2.3 انتخاب کننده قاعده مبتنی بر درخت تصمیم گیری
2. 3. ساخت درخت تصمیم
2.4 استراتژی زمانبندی
3. کاربرد
3. 1. توصیف سیستم
3.2 قوانین توزیع
3. 3. طراحی و نتایج تجربی
4. نتیجه گیری ها

بخشی از ترجمه فارسی مقاله:

چکیده
فروشگاه دارای چند ورودی با جریان ترکیبی که به طور معمول در صنعت الکترونیک یافت می شود، یک سیستم گسترش یافته از فروشگاه با جریان عادی به گونه ای است که یک یا چند دستگاه موازی در هر مرحله سریال وجود دارند و هر کار دارای جریان محصول چند ورودی است، به عنوان مثال، یک کار ممکن است چندین بار در یک مرحله انجام شود. در میان مسائل عملیاتی در فروشگاه هایی دارای چند ورودی با جریان ترکیبی ، ما روی مسئله زمانبندی تمرکز می کنیم که تخصیص کارها را به دستگاه ها در هر مرحله و همچنین دنباله کارهای منسوب شده به هر دستگاه را تعیین می نماید. بر خلاف رویکرد نظری در زمانبندی فروشگاه دارای چند ورودی با جریان ترکیبی، ما یک مکانیسم زمانبندی زمان واقعی را با درخت تصمیم گیری در هنگام انتخاب قواعد توزیع مناسب نشان می دهیم. درخت تصمیم گیری، یکی از معمول مورد استفاده از تکنیک های داده کاوی، اتخاذ برای از بین بردن بار محاسباتی مورد نیاز برای انجام شبیه سازی اجرا می شود را انتخاب کنید قوانین توزیع. برای نشان دادن مکانیزم پیشنهادی در این مطالعه، یک مطالعه موردی را در یک خط تولید صفحه نمایش کریستالی ترانزیستور مایع فیلم نازک (TFT-LCD) انجام شده است و نتایج به دست آمده برای معیارهای مختلف عملکرد سیستم گزارش می شوند.
کلمات کلیدی:فروشگاه های دارای چند ورودی با جریان ترکیبی،زمانبندی زمان واقعی،درخت های تصمیم گیری
مطالعه موردی
1. مقدمه
یک فروشگاه جریان ترکیبی، سیستم تولید گسترش یافته از فروشگاه جریان عادی، شامل دو یا چند مرحله به صورت سری است و یک یا چند دستگاه موازی در هر مرحله وجود دارد. به طور کلی، دستگاه های موازی در هر مرحله برای هدف افزایش بهره وری و همچنین انعطاف پذیری اضافه شده اند. فروشگاه جریان ترکیبی را می توان در انواع مختلفی از صنایع یافت. یکی از آنها صنعت الکترونیک است، مانند ساخت نیمه هادی ویفر، تولید برد مدار چاپی (PCB) تولید صفحه نمایش کریستال ترانزیستور-مایع فیلم نازک (TFT-LCD)، و غیره. علاوه بر این، صنایع مختلف سنتی، از جمله مواد غذایی، مواد شیمیایی و فلزی، دارای فروشگاه های مختلف جریان ترکیبی هستند.
فروشگاه های جریان ترکیبی را می توان با توجه به جریان های محصول به دو نوع طبقه بندی نمود: (الف) فروشگاه ها با جریان یک سویه. و (ب) فروشگاه ها با دارای چند جریان ورودی. در اینجا، جریان یک سویه این مفهوم را میرساند که هر کار در مرحله اول شروع می شود و پس از در آخرین مرحله به اتمام می رسد. از سوی دیگر، در مورد جریان دارای چند ورودی، هر کار ممکن است به هر مرحله سریال دو یا چند بار بازدید کند. به عنوان مثال، ساخت ویفر نیمه هادی و خطوط تولید TFT-LCD دارای دارای جریان چند ورودی است. به عبارت دیگر، هر یک از بازدیدها از برخی از مرحله تولید سریال مشخص شده مربوط به یک لایه است که برای مدارات مورد نیاز ساخته شده است. در مقایسه با جریان یک سویه، جریان های دارای چند ورودی به طور کلی عملیات سیستم را بسیار پیچیده تر می سازد.
این مقاله روی مسئله زمانبندی در فروشگاه های جریان ترکیبی با جریان های محصول دارای چند ورودی، به نام زمانبندی فروشگاه دارای چند ورودی با جریان ترکیبی تمرکز نموده است. تصمیمات اصلی عبارتند از: (الف) تخصیص کارها به دستگاه در هر مرحله. و (ب) دنباله کارهای داده شده به هر دستگاه. در واقع، این تحقیق از یک سیستم تولید TFT-LCD با تعداد زیادی از فرآیندهای پیچیده و جریان محصول دارای چند ورودی انگیزه گرفته است. همانطور که قبلا گفته شد، جریان محصول دارای چند ورودی عملیات خود را بسیار پیچیده تر می سازد و از این رو اجرای سیستم بدتر و بدتر می شود. به منظور بهبود عملکرد سیستم، توسعه و پیاده سازی سیستم زمانبندی کارآمد لازم است. یکی از بخش های اصلی آن، روش زمانبندی زمان واقعی قوی است که ویژگی های پویا از سیستم تولید TFT-LCD واقعی را در نظر می گیرد.
بسیاری از مطالعات قبلی در مورد زمانبندی فروشگاه دارای چند ورودی با جریان ترکیبی نظری هستند، به این معنا که الگوریتم های پیچیده پس از توسعه و تجزیه و تحلیل مدلهای ریاضی با مفروضات مختلف ابداع شدند. (Linn و Zhang (1999) را ببینید برای بررسی نوشته ها در مورد زمانبندی فروشگاه جریان ترکیبی). برای مثال، Bertel و Billaut (2004) یک الگوریتم ژنتیکی را برای زمانی بندی فروشگاه دارای چند ورودی با جریان ترکیبی پیشنهاد دادند که تعداد وزنی کارهای دارای تاخیر را به حداقل می رساند، و Choi، Kim و Lee (2005) چندین الگوریتم زمانبندی فهرست را برای این مسئله با هدف به حداقل رساندن تاخیر کل پیشنهاد دادند. به تازگی، Choi و همکاران. (2009) مسئله زمانبندی دو مرحله فروشگاه دارای چند ورودی با جریان ترکیبی را با هدف به حداقل رساندن گستره زمانی کار در نظر گرفتند، در حالیکه تاریخ های موعد تحویل مجاز ماکزیمم را برآورده نمودند و الگوریتم های ابتکاری مختلف را پیشنهاد نمودند. همچنین، Graves، Meal، Stefek، و Zeghmi (1983) و Hsu و Shamma (1997) زمانبندی فروشگاه جریان دارای چند ورودی، یک مورد خاص از زمانبندی فروشگاه دارای چند ورودی با جریان ترکیبی را در نظر گرفتند. اگر چه این مقالات باید به معنای نظری کمک نمایند، کاربردهای آنها محدود است چرا که آنها ذاتا نسخه های ساکن از مسئله هستند.
زمانبندی زمان واقعی، یکی از روش های زمانبندی عملی، موضوع مهمی است که بر اساس آن، تعدادی از تحقیقات قبلی انجام شده است. Yamamoto و Nof (1985) زمانبندی و روش برنامه ریزی مجددی را پیشنهاد دادند که در آن یک برنامه زمانبندی اولیه در آغاز ایجاد می شود، و تجدید نظرهای برنامه، هر زمان که تغییرات عملیاتی وجود دارد انجام می شود و Church و Uzsoy (1992) سیاست های دوره ای را برای زمانبندی مجدد در دستگاه های تک و موازی در محیط پویا مورد تجزیه و تحلیل قرار دادند. Kim و Kim (1994) یک مکانیزم زمانبندی زمان واقعی مبتنی بر شبیه سازی را برای سیستم های تولید انعطاف پذیر پیشنهاد دادند که در آن قوانین توزیع به صورت پویا مبتنی بر اطلاعات به دست آمده از شبیه سازی متغیر هستند و بعداً مدل آنها توسط Jeong و Kim (1998) گسترش یافت که در آن یک چارچوب نظام مند همراه با استراتژی های زمانبندی پیشنهاد شد که نقطه زمانی را تعیین کی می نمود که یک قانون توزیع جدید انتخاب می شود. Chang (1997) مکانیزم زمان واقعی زمانبندی مبتنی بر شبیه سازی دیگری را پیشنهاد داد که در آن دفعات صف بندی برای عملیات های باقی مانده از کارها تخمین زده می شوند و سپس در طرح زمانبندی موجود فروشگاه های پویا گنجانده می شوند. همچنین، Cowling و Johansson (2002) یک چارچوب کلی را برای استفاده از اطلاعات زمان واقعی به منظور بهبود تصمیم گیری زمانبندی ارائه نمودند. برای امکانات ساخت ویفر نیمه هادی، Kim، Shim، Choi، و Hwang (2003) روش ساده ای را برای انجام کارآمد و توزیع به موقع بر اساس زمانبندی شبیه سازی زمان واقعی پیشنهاد نمودند و Min و Yih (2003) با ترکیب سیاست های توزیع دستگاه و وسیله نقلیه، اقدام به بهبود عملکرد سیستم نمودند.
بر خلاف روش های موجود که در بالا توضیح داده شد، ما یک مکانیسم زمانبندی زمان واقعی را نشان می دهیم که در آن درخت تصمیم برای انتخاب یک قاعده توزیع مناسب در پایان هر دوره نظارت استفاده می شود به طوری که بار محاسباتی مورد نیاز برای انجام شبیه سازی حذف می شود. در اینجا، دوره نظارت، دوره زمانی است که در طی آن یک قاعده توزیع قبل از در نظر گرفتن تغییر قانونی مقرر می شود. همچنین، درخت تصمیم، یک مدل شماتیک برای تعیین یکی از گزینه های در دسترس برای یک تصمیم گیرنده، با استفاده از اطلاعات به دست آمده از داده های اولیه ساخته می شود. مکانیسم زمانبندی زمان واقعی پیشنهاد شده در این مقاله با یک مطالعه موردی در یک خط تولید TFT-LCD نشان داده شده است و نتایج آزمون برای معیارهای مختلف عملکرد سیستم گزارش شده است.
اگر چه تعدادی از مقالات تحقیقاتی قبلی در مورد زمانبندی در سیستم های تولید نیمه هادی وجود داشته است، یعنی، نمونه فروشگاه های دارای جریان ترکیبی با چند ورودی، آنها دارای کاربردهای محدودی هستند، زیرا از نظر ماهیتی آفلاین می باشند. برای مثال Wein (1988)، Glassey و Resende (1988)، Lu، Ramaswamy، و Kumar (1994)، Kim، Lee، Kim، و Roh (1998)، Hung و Chen (1998) را ببینید. به عبارت دیگر، بسیاری از آنها، روش های زمانبندی خاصی را نشان می دهند که کیفیت های راه حل آنها با شبیه سازی استاتیک و آفلاین نشان داده می شوند. همچنین، رویکردهای زمانبندی زمان واقعی موجود برای تولید نیمه هادی، قوانین توزیع اولویت را با استفاده از اطلاعات به دست آمده از اجراهای شبیه سازی انتخاب می نماید و از این رو آنها ممکن است به مقدار قابل توجهی از بار محاسباتی نیاز داشته باشند. بر خلاف این، ما یک مکانیسم زمانبندی زمان واقعی را نشان می دهیم که سرعت تصمیم گیری زمانبندی را با استفاده از درخت تصمیم گیری افزایش می دهد. توجه داشته باشید که اجرای سیستم به طور مستقیم سرعت سیستم زمانبندی را تحت تاثیر قرار می دهد و از این رو تصمیمات و اقدامات زمانبندی نیز در زمان واقعی باید ساخته شوند.
این مقاله به شرح زیر است. در بخش بعدی، ما مکانیسم زمانبندی زمان واقعی مبتنی بر درخت تصمیم گیری را توضیح می دهیم. الگوریتم ساخت درخت تصمیم گیری نیز توضیح داده می شود. مطالعه موردی در مورد خط تولید TFT-LCD در بخش 3 گزارش شده است. در نهایت، بخش 4 نتایج اصلی را خلاصه می کند، نتیجه گیری ها را ارائه می دهد، و برخی حوزه ها برای تحقیقات بیشتر را توصیف می کند.

بخشی از مقاله انگلیسی:

Abstract

A reentrant hybrid flow shop, typically found in the electronics industry, is an extended system of the ordinary flow shop in such a way that there exist one or more parallel machines at each serial stage and each job has the reentrant product flow, i.e., a job may visit a stage several times. Among the operational issues in reentrant hybrid flow shops, we focus on the scheduling problem that determines the allocation of jobs to the machines at each stage as well as the sequence of the jobs assigned to each machine. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a realtime scheduling mechanism with a decision tree when selecting appropriate dispatching rules. The decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported for various system performance measures.

1. Introduction

A hybrid flow shop, an extended production system of the ordinary flow shop, consists of two or more stages in series and there exist one or more parallel machines at each stage. In general, the parallel machines at each stage are added for the objective of increasing productivity as well as flexibility. The hybrid flow shop can be found in various types of industries. The most representative one is the electronics industry, such as semiconductor wafer fabrication, printed circuit board (PCB) manufacturing, thin film transistor-liquid crystal display (TFT-LCD) manufacturing, etc. In addition, various traditional industries, such as food, chemical and steel, have various hybrid flow shops. Hybrid flow shops can be classified into two types according to product flows: (a) those with unidirectional flows; and (b) those with reentrant flows. Here, the unidirectional flows imply that each job starts at the first stage and finishes at the last stage. On the other hand, in the reentrant flows, each job may visit each serial stage two or more times. For example, semiconductor wafer fabrication and TFT-LCD manufacturing lines have the reentrant flows. In other words, each visit of certain specified serial production stage corresponds to a layer that is built up for required circuits. Compared with the unidirectional flows, the reentrant flows generally make system operations much more complicated. This paper focuses on the scheduling problem in hybrid flow shops with reentrant product flows, called reentrant hybrid flow shop scheduling in this paper. The main decisions are: (a) allocation of jobs to machines at each stage; and (b) sequence of the jobs assigned to each machine. In fact, this research was motivated from a TFT-LCD manufacturing system with a large number of complex processes and reentrant product flows. As stated earlier, the reentrant product flows make its operations much more complicated and hence the system performances get worse. To improve the system performances, it is needed to develop and implement an efficient scheduling system. One of its main parts is the robust realtime scheduling methodology that considers the dynamic features of the real TFT-LCD manufacturing system. Most of the previous studies on reentrant hybrid flow shop scheduling are theoretic in the sense that sophisticated algorithms were devised after developing and analyzing mathematical models with various assumptions. (See Linn and Zhang (1999) for a literature review on hybrid flow shop scheduling.) For example, Bertel and Billaut (2004) suggested a genetic algorithm for reentrant hybrid flow shop scheduling that minimizes the weighted number of tardy jobs, and Choi, Kim, and Lee (2005) suggested several list scheduling algorithms for the problem with the objective of minimizing total tardiness. Recently, Choi et al. (2009) considered the two-stage reentrant hybrid flow shop scheduling problem for the objective of minimize makespan while meeting the maximum allowable due dates, and suggested several heuristic algorithms. Also, Graves, Meal, Stefek, and Zeghmi (1983) and Hsu and Shamma (1997) considered reentrant flow shop scheduling, a special case of the reentrant hybrid flow shop scheduling. Although these articles have contributions in the theoretical sense, their applications are limited since they are inherently static versions of the problem. Real-time scheduling, one of practical scheduling approaches, is an important topic on which a number of previous researches have been done. Yamamoto and Nof (1985) proposed a scheduling and rescheduling method in which an initial schedule is generated at the beginning, and schedule revisions are done whenever there are significant operational changes, and Church and Uzsoy (1992) analyzed periodic and even-driven policies for rescheduling in single and parallel machines in the dynamic environment. Kim and Kim (1994) suggested a simulation-based real-time scheduling mechanism for flexible manufacturing systems, in which dispatching rules vary dynamically based on information obtained from simulation, and later, their model was extended by Jeong and Kim (1998) in that a systematic framework is suggested together with scheduling strategies that determine the point of time when a new dispatching rule is selected. Chang (1997) suggested another simulation-based real-time scheduling mechanism in which queueing times for the remaining operations of jobs are estimated and then incorporated into the existing scheduling heuristics for dynamic job shops. Also, Cowling and Johansson (2002) provided a general framework for using real-time information to improve scheduling decisions. For semiconductor wafer fabrication facilities, Kim, Shim, Choi, and Hwang (2003) suggested simplification methods to carry out efficient and prompt dispatching in simulation-based real-time scheduling, and Min and Yih (2003) attempted to improve system performances by combining machine and vehicle dispatching policies. Unlike the existing approaches explained above, we suggest a real-time scheduling mechanism in which the decision tree is used to select an appropriate dispatching rule at the end of each monitoring period so that the computational burden required for carrying out simulation runs can be eliminated. Here, the monitoring period is the time period during which a dispatching rule is maintained before considering the rule change. Also, the decision tree, a schematic model to determine one of the alternatives available to a decision maker, is constructed using the information obtained from preliminary data. The real-time scheduling mechanism suggested in this paper is illustrated with a case study on a TFT-LCD manufacturing line, and the test results are reported for various system performance measures. Although there have been a number of previous research articles on scheduling in semiconductor manufacturing systems, i.e., typical reentrant hybrid flow shops, they have limited applications since they are off-line in nature. See Wein (1988), Glassey and Resende (1988), Lu, Ramaswamy, and Kumar (1994), Kim, Lee, Kim, and Roh (1998), Hung and Chen (1998) for examples. In other words, most of them suggest certain scheduling methods whose solution qualities were shown with static and off-line simulations. Also, the existing real-time scheduling approaches for semiconductor manufacturing select priority dispatching rules using the information obtained from simulation runs and hence they may require significant amount of computational burden. Unlike these, we suggest a real-time scheduling mechanism that increases the speed of the scheduling decisions using the decision tree. Note that the system performances are directly affected by the speed of scheduling system and hence scheduling decisions and actions also have to be made in real-time. This paper is organized as follows. In the next section, we explain the decision tree based real-time scheduling mechanism. The algorithm to construct the decision tree is also explained. The case study on the TFT-LCD manufacturing line is reported in Section 3. Finally, Section 4 summarizes the main results, gives the conclusions, and describes some areas for further research.