This paper considers identical parallel-machine scheduling problem with past-sequence-dependent (psd) delivery times and learning effect. In electronic manufacturing industry, an electronic component may be exposed to certain electromagnetic field and requires an extra time for eliminating adverse effect after the main processing. The extra time is modeled as past-sequence-dependent delivery time in the literature, which is proportional to the waiting time in the system. It is also observed that the learning process reflects a decrease in the processing time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. In practice, one often has to deal with the scheduling problems with psd delivery times and learning effect. Identical parallel-machine setting is considered because the occurrence of resources in parallel is common in the real world. In this paper, three objectives are the minimization of the total absolute deviation of job completion times, the total load on all machines and the total completion time. We develop polynomial algorithms to optimally solve these problems

چکیده

در این مقاله، مسئله ی زمان بندی ماشین‌آلات موازیِ یکسان، با در نظر گرفتن زمان های تحویل وابسته به توالی گذشته (psd) و تأثیر یادگیری در نظر گرفته خواهد شد. در صنعت تولید تجهیزات الکترونیکی، یک مؤلفه ی الکترونیکی ممکن است در معرض یک میدان الکترومغناطیسی خاصی قرار گرفت و پس از پردازش اصلی، نیاز به زمان بیشتری برای دفع تأثیر سوء و مغایر ناشی از این میدان داشته باشد. در حوزه و ادبیات مسائل زمان بندی، این زمان اضافی به عنوان یک زمان تحویل وابسته به توالی گذشته مدل سازی می گردد که متناظر با زمان انتظار در سیستم می باشد. همچنین مشاهده شده است که فرآیند یادگیری می تواند کاهش زمان پردازش را به عنوان تابعی از تعداد تکرارها –یعنی به عنوان تابعی از موقعیت یک کار در یک توالی- به همراه داشته باشد. در عمل، ما با مسائلِ زمان بندی همراه با زمان های تحویل psd و اثر یادگیری همراه هستیم. از این جهت اقدام به انتخاب بستر ماشین‌آلات-موازی یکسان نمودیم، چرا که رخداد منابع به شکلی موازی در دنیای واقعی امری رایج است. در این مقاله، سه هدف را دنبال می کنیم: به حداقل رساندن انحراف مطلق کلِ زمان تکمیل کار، به حداقل رساندن بار همه ی ماشین ها و به حداقل رساندن زمان تکمیل کل. الگوریتم های چند جمله ای را نیز به منظور حل بهینه ی این مسائل توسعه داده ایم.

1-مقدمه

در بسیاری از صنایع، محیط تولیدی از تأثیر قابل ملاحظه ای بر روی زمان پردازش کارها برخوردار می باشد. در صنعت تولید تجهیزات الکترونیکی، یک مؤلفه ی الکترونیکی ممکن است در زمانی که در ناحیه ی پیش‌ پردازش ماشین در انتظار پردازش می باشد، در معرض میدان های الکترومغناطیسی یا رادیواکتیو قرار گرفته و در همین راستا، متصدیان رگولاتوری (سازمان تنظیم مقررات در محیط تولید) باید این مؤلفه را برای یک مدت زمانی که متناسب با قرارگیری این مؤلفه در معرض میدان های الکتریکی می باشد، مورد فرآوری قرار دهند (به عنوان مثال این مؤلفه را باید در یک محلول شیمیایی که می تواند تأثیرات خاص میادین رادیواکتیو/ الکترومغناطیسی را از بین ببرد قرار داد)...