Scheduling Deteriorating Jobs on a Single Machine with a Common Due Window
In operational systems of firms,scheduling significantly influences the performance.At the same time,with the application of just-in-time concept,due-date assignment also plays an important role in operational systems,which requires customer orders should be finished at a assigned time.In brief,through delicate scheduling rule and appropriate due-date assignment,firm’s limited production resource can be utilized more efficiently,and at the same time they can be better matched with varied customer demands.Thus,the decisions of scheduling and due-date assignment are usually decided simultaneously.However,for many practical applica-tion scenarios,it is allowable to complete customer orders within a period.Under these cases,decision makers need to determine due windows for customer orders instead of due dates.A due window for a job consists of three parts:the starting time of due window,the finishing time of due window and the due window size.In literature on due-window assignment scheduling problems,decision makers often assign the same due window for all customers to maintain a unified customer service policy.But the size of due window can be fixed directly by decision makers or can be negotiated with customers.In addition,the existing researches always assume jobs to be finished before the starting time of due window or after the finishing time of due window would incur cost due to earliness or tardiness,but jobs to be completed within due window would not result in any cost.Besides the influence of due window assignment method on formulating and solving due-window assignment scheduling prob-lems,other interference factors existing in operational systems also exert an influence.Among these factors,jobs deterioration would change their actual processing times,and further influences the way the due-window assign-ment scheduling problem is solved.In the field of studies on due-window assignment scheduling problems with deterioration jobs,it is often assumed that the actual processing time of a job is a linear function of its starting processing time and deterioration rate.This paper studies the due-window assignment scheduling problem with deteriorating jobs in a single machine environment.The common due-window assignment method is applied to assign a due window for all jobs,and the beginning time of due window and the size of due window are decision variable.The actual processing time of a job is a linear function of its starting processing time and deterioration rate,and jobs have various deterioration rates.The objective of the problem is to simultaneously determine the scheduling policy and the common due window for all jobs,so as to minimize the total costs associated with earliness,tardiness and due-window assignment.To deal with the problem that we consider,we first introduce some notations and formally describe the problem with classical scheduling language.On the basis,we analyze the property of optimal due-window assignment and propose the optimal rule to assign due windows for all jobs.Then,we analyze the property of optimal schedule and propose the specific rule to schedule early jobs,tardy jobs and jobs to be completed within due window,respectively.Based on this,we point out the way jobs are scheduled in different sets,which are the set of early jobs,the set of tardy jobs and the set of jobs to be finished within due window.With those conclusions about optimal schedule and due-window assignment,we derive the way the studied problem is solved and propose the solution algorithm formally.For the proposed algorithm,we finally analyze the computational complexity by computing the computational time for each step in the algorithm.By careful analysis,we conclude that the proposed optimal algorithm is polynomial.
single machine schedulingcommon due windowdeteriorating jobspolynomial algorithm
国家科技期刊平台
NSTL
万方数据
