Optimal Scheduling Strategies for Minimizing Completion Time and Cost
In this study, optimal scheduling strategies are explored to minimize total weighted completion time considering non-increasing time slot costs. Various models and algorithms are discussed, including approaches to execute jobs efficiently based on their characteristics. The importance of processing time, weight, and cost in determining optimal schedules is highlighted, along with the influence of linear time slot cost decrease on scheduling decisions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On Scheduling with Non-increasing Time Slot Cost to Minimize Total Weighted Completion Time On Scheduling with Non-increasing Time Slot Cost to Minimize Total Weighted Completion Time On Scheduling with Non-increasing Time Slot Cost to Minimize Total Weighted Completion Time On Scheduling with Non-increasing Time Slot Cost to Minimize Total Weighted Completion Time Yingchao ZHAO, Caritas Institute of Higher Education Xiangtong QI, HKUST Minming LI Minming LI, City University of Hong Kong
Traditional scheduling objective minimizing makespan minimizing total completion time minimizing total flow time. Wan and Qi (Naval Research Logistics) proposed the model that considers both traditional objective and time slot cost. Kulkarni and Munagala (WAOA 2012)studied online algorithms to minimize the total weighted completion time plus time slot costs. Leonardi et al. (MAPSP 2013) designed a PTAS for the offline version of the problem.
Increasing Trivial Execute the jobs as early as possible Decreasing Linear decreasing Accelerative decreasing Decelerative decreasing General decreasing Objective Minimize: total weighted completion time + time slot costs
(t) t
For each job i: Processing time pi Weight wi The time slot cost satisfies We give a polynomial time algorithm to get the optimal schedule for this problem. Given two jobs, which should be processed earlier? Given a job, when should it be processed? k- k+1= , >0
If the time slot cost decreases as a linear function with respect to time k, then there exists an optimal schedule to the problem in which jobs are scheduled in WSPT (Weighted Shortest Processing Time) order.
For a job with processing time p and weight w If w/p> , process this job as early as possible If w/p< , process this job as late as possible If w/p= , the job has the same cost no matter when it is processed
t w/p> w/p= w/p< 0 K t 0 K t 0 K Sort the jobs according to decreasing w/p. Partition jobs into three sets: J1, J2, J3 Process J1 and J2 from time zero, and process J3 as late as possible. Solved in polynomial time!
(t) t
The time slot cost satisfies For each job Processing time p Weight w Worst starting time k , k +1 - k +p+1> w > k - k +p k- k+1> k-1- k, for 1<k<K Every job has a worst starting time There is only one possible idle time interval in an optimal schedule.
K 0 k If a job starts before its worst starting time k , then there is no idle time before it in the optimal schedule. If a job starts after its worst starting time k , then there is no idle time after it in the optimal schedule. If a job starts at its worst starting time k , then there is no idle time before and after it in the optimal schedule.
In an optimal schedule, the jobs are partitioned into two parts. The first part starts from time zero. The second part ends at time K. In each part, jobs are processed in WSPT order. 0 K How to partition jobs?
f(m,x,y) denotes the minimum cost for jobs 1 to m, where the first part ends at x, and the second part starts at y. 0 x y jobs in the same part are scheduled in WSPT order Where is job m? Job m is in the last job of in the first part need to know f(m-1, x-pm, y) Job m is in the last job of in the second part O(nP2) need to know f(m-1, x, y)
(t) t
The time slot cost satisfies For each job Processing time p Weight w Preferred starting time: k*, Preferred processing interval: [k*, k*+p] k- k+1< k-1- k, for 1<k<K k*+1 k*+p+1> w > k* - k*+p
k* k*+p K 0 If a job starts before its preferred starting time k*, the earlier it is processed, the more cost it will have. If a job starts after its preferred starting time k*, the later it is processed, the more cost it will have. If a job starts at its preferred starting time k*, it will have the least possible cost.
Job i Job j > > wi/pi wj/pj If two jobs preferred processing intervals have no overlap, then the job with earlier preferred starting time has greater ratio of w/p than the other job. Job i Job j > > wi/pi wj/pj If two jobs preferred processing intervals have overlap, but not completely contain each other, then the job with earlier preferred starting time has greater ratio of w/p than the other job.
The jobs are scheduled in WSPT order in the optimal solution. If two jobs are adjacent in WSPT order and their preferred processing intervals have overlap, then there exists no idle time slot between these two jobs in the optimal solution. Algorithm: 1. sort by WSPT 2. merge and replace 3. assign to preferred intervals Job i Job i Job j (wi, pi) (wi +wj, pi+pj) (wj, pj) O(n2)
(t) t
Theorem 1. The problem with arbitrary non- increasing time slot cost is NP-hard in the strong sense. 3-Partition Instance: n=3q integers a1, a2, , a3q integer b with b/4<aj<b/2 sum(aj)=q*b Scheduling Instance: n=3q jobs processing time aj, weight *aj K=q(b+1)
Polynomial time algorithm for the accelerative decreasing case More classes of decreasing cost Other objectives besides total weighted completion time Multiprocessor
J. Kulkarni and K. Munagala, Algorithms for cost aware scheduling, in Proceedings of 10th International Workshop on Approximation and Online Algorithms (WAOA 2012), 201-214. S. Leonardi, N. Megow, R. Rischke, L. Stougie, C. Swamy and J. Verschae, Scheduling with time-varying cost: deterministic and stochastic models, in 11th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2013). G. Wan and X. Qi, Scheduling with variable time slot costs, Naval Research Logistics, 57 (2010) 159-171.
