Scheduling problems with a weight-modifying-activity
- PDF / 536,509 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 225 Views
Scheduling problems with a weight-modifying-activity Gur Mosheiov1 · Daniel Oron2 Accepted: 29 August 2020 © Crown 2020
Abstract We study single machine scheduling problems with an additional option of performing a weight-modifying-activity. If such an activity is performed, the cost of subsequent jobs is reduced, as reflected by smaller job-weights. We focus first on minimizing total weighted completion time. A pseudo-polynomial dynamic programming algorithm is introduced for this problem. Several special cases of unit processing time jobs are solved in polynomial time. We also solve in polynomial time (an extension of) the minmax version of the problem, by adapting the well-known Lawler’s Algorithm for minimizing maximum cost on a single machine. Keywords Scheduling · Single machine · Weight-modifying-activity · Total weighted completion time · Dynamic programming
1 Introduction Scheduling with a rate-modifying-activity has become a popular topic for scheduling researchers in recent years. In this class of problems, the scheduler may insert a certain activity which increases the efficiency of the system, as reflected by some reduction in the processing times of the jobs assigned after this activity. Scheduling with a rate-modifyingactivity was introduced by Lee and Leon (2001), who focused on single machine problems with the objectives of makespan, total (weighted) flow-time and maximum lateness. Many extensions have been studied since then, including Lee and Lin (2001), Mosheiov and Oron (2006), Zhao et al. (2009), Wang and Wang (2010), Cheng et al. (2012), Mor and Mosheiov (2012), Rustogi and Strusevich (2012), Zhao and Tang (2012), Chang et al. (2014), Chen et al. (2014), Mor and Mosheiov (2014), Wang et al. (2016), Zhu et al. (2017) and Ozturkoglu (2017). We refer the reader to the recently published book (“Scheduling with Time-Changing Effects and Rate-Modifying Activities”, Strusevich and Rustogi 2017), for solution algorithms of many scheduling problems with different combinations of machine settings and objective functions, and for various applications.
B
Daniel Oron [email protected]
1
School of Business Administration, The Hebrew University, Jerusalem, Israel
2
The University of Sydney Business School, The University of Sydney, Sydney, NSW 2006, Australia
123
Annals of Operations Research
In this paper we consider a different type of a rate-modifying activity, which, to the best of our knowledge, has never been studied in the context of scheduling. In our proposed model, this (optional) rate-modifying-activity impacts the cost of subsequent jobs rather than their processing times. Thus, a job which is processed after this activity will incur a lower cost. Specifically, if a job of a given weight (reflecting its cost) is delayed and processed after the rate-modifying-activity, its weight is reduced. We thus focus in this paper on scheduling problems with a Weight-Modifying-Activity (denoted WMA). Here, the decision whether or not to perform WMA creates a trade-off between the loss of
Data Loading...
