برنامه ریزی شغلی برای به حداقل رساندن وزن واریانس زمان انتظار شغل
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
20084 | 2007 | 16 صفحه PDF |
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Industrial Engineering, Volume 52, Issue 1, February 2007, Pages 41–56
چکیده انگلیسی
This study considers the job scheduling problem of minimizing the weighted waiting time variance (WWTV) of jobs. It is an extension of WTV minimization problems in which we schedule a batch of n jobs, for servicing on a single resource, in such a way that the variance of their waiting times is minimized. WWTV minimization finds its applications for job scheduling in manufacturing systems with earliness and tardiness (E/T) penalties, in computer and networks systems for the stabilized QoS, and in other fields where it is desirable to minimize WWTV of jobs with different weights for priorities. We formulate a WWTV problem as an integer programming problem, prove the V-shape property for agreeably weighted WWTV problems and the nondelay property for general WWTV problems, and discover the strong V-Shape tendency of the optimal job sequences for this problem. Two job scheduling algorithms, Weighted Verified Spiral (WVS) and Weighted Simplified Spiral (WSS), are developed for the WWTV problems. Numerical testing shows that WVS and WSS significantly outperform existing WWTV algorithms.
مقدمه انگلیسی
The single machine weighted waiting time variance (WWTV) minimization problem, denoting by 1∥WWTV , is to schedule the jobs in a batch on a single machine so as to minimize the weighted waiting time variance of the jobs as follows where Π is the set of all the permutations of the n jobs, v i(λ ) is the weight of the job on position i to indicate its priority, W i(λ ) is the waiting time of the job on position i and View the MathML sourceW¯(λ) is the weighted average waiting time of the jobs for a given sequence λ. A greater value of vi means a higher priority. It is an extension of the WTV problem in which jobs are considered to have the same weight ( Merten and Muller, 1972 and Ye et al., 2006). WWTV minimization has many applications in different fields. WWTV problems are closely related to weighted common due date problems. A weighted common due date problem can be modeled as finding an optimal common due date, d , to minimize the mean squared deviation (MSD), ∑vi(Wi-d)2∑vi(Wi-d)2. It can be obtained as View the MathML source(∑vi∗Wi∗)/∑vi∗, where View the MathML sourcevi∗ and View the MathML sourceWi∗ are the weight and waiting time of the jobs in the optimal WWTV sequence, respectively, since MSD is the second moment about d. The connection between the WWTV minimization problems and the weighted common due date problems suggests the applicability of putting WWTV minimization for scheduling problems with earliness and tardiness (E/T) penalties in manufacturing systems ( Baker and Scudder, 1990, Cheng and Gupta, 1989 and Verma and Dessouky, 1998). This is an extension of the relationship between the WTV problem and common due date problem or mean squared deviation (MSD) problem ( Bagchi et al., 1987, Cheng and Gupta, 1989, Cheng and Kovalyov, 1996, Cheng et al., 2002 and Panwalker et al., 1982). It is shown that the CTV problem is equivalent to the unconstrained version of the mean squared deviation minimization problem ( Bagchi et al., 1987). In addition to applications to job scheduling for E/T minimization in manufacturing systems, WWTV is in connection with providing stabilized Quality of Service (QoS) in computers and networks (Ye et al., 2006). For instance, the data packets from WTV-sensitive applications (audio or video players) should have higher priorities of data transmission against other data packets (emailing or web browsing) arriving at a router. It is desirable to minimize the weighted WTV of the data packets to stabilize the router so that higher priority data packets get more consistent service performance or stable QoS. WWTV minimization may also find application in other service facilities where it is desirable to serve the jobs with different weights in stability. The authors (Merten & Muller, 1972) first introduce the weighted variance minimization for file organization problems in which it is desirable to treat user’s requests to data file in a stable manner. They propose a problem model that involves arbitrary job processing times and weights. One special case of the model, in which the jobs have equal weights, has received extensive studies since then. The authors (Merten & Muller, 1972) find that a sequence minimizing the variance of flow-time or completion time is antithetical to a sequence minimizing the variance of waiting time if the jobs have the same weight. An optimality condition of a WTV problem is shown in (Cai, 1996, Eilon and Chowdhury, 1977 and Mittenthal et al., 1995) that the optimal sequence must be V-shaped, which means that the jobs before the job with the shortest processing time are sorted in a descending order while the jobs after the smallest job are sorted in an ascending order. The author (Schrage, 1975) considered the optimal sequences for problems with up to five jobs and showed that the longest job must be the first to be processed to minimize the completion time variance (CTV). The author (Schrage, 1975) conjectured the positions of the three longest jobs which were proven in (Hall & Kubiak, 1991). A counter example shows that the conjecture about the fourth longest job is incorrect in (Kanet, 1981). The author in (Kubiak, 1993) proves that the CTV problem on a single machine is NP-hard. The bounds for the position of the smallest job in the CTV problem are established in (Manna & Prasad, 1999). The author in (Kubiak, 1995) formulates the CTV problem as a problem of maximizing a zero-one quadratic function which is a sub-modular function with a special cost structure. The variance of job completion time with bi-criteria extension is investigated in (De et al., 1992 and De et al., 1996). A branch and bound algorithm to minimize CTV is given in (Viswanathkumar & Srinivasan, 2003) and a tabu search-based solution is developed in (Al-Turki, 2001). The pseudo polynomial algorithms and fast polynomial approximation schemes for CTV minimization problems are given in (Cheng and Kovalyov, 1996, Kubiak et al., 2002 and Manna and Prasad, 1997). A sufficient optimality condition for stochastic CTV is discussed in (Cai, 1996). More heuristic methods are developed for CTV/WTV problems in (Al-Turki et al., 2001, Eilon and Chowdhury, 1977, Gowrishankar et al., 2001, Kanet, 1981, Sharma, 2002, Vani and Raghavachari, 1987 and Ye et al., 2006). We can see that there are extensive studies in the literature about WTV problems. However, studies on the WWTV problem are limited. The author in (Cai, 1995) considers the minimization of “agreeably weighted” completion time variance on a single machine. The “agreeably weighted” setting means that pi < pj implies vi ⩾ vj, where pi, vi, pj and vj are the processing time and the weight of job i and j, respectively. This indicates that a smaller job has a greater weight value for a higher priority. The agreeably weighed condition is a strong assumption. In many cases, the weights of the jobs are independent of the processing times of the jobs. In this paper, we will address how to reduce WWTV under different weighted scenarios including the special case studied in (Cai, 1995). The rest of the paper is organized as follows. In Section 2, we give a mathematical formulation of the WWTV problem. In Section 3, we prove the V-shape property for agreeably weighted WWTV problems and nondelay property for general WWTV problems and analyze the optimal sequences of general WWTV problems and find the strong V-Shape tendency of the optimal sequences in a general sense. Two heuristic methods are developed to construct job sequences for a WWTV problem. The testing results are given in Section 5. In Section 6, we conclude this paper.
نتیجه گیری انگلیسی
In this study we investigate the weighted waiting time variance minimization problem for a single resource on computers and networks. We formulate this problem as an integer programming problem, prove the V-shape property for agreeably weighted WWTV problems and nondelay property for general WWTV problems, find the V-Shape tendency of the optimal sequences of general WWTV problems, and develop Weighted Verified Spiral (WVS) and Weighted Simplified Spiral (WSS) heuristic methods. We test small-size and larger-size problems in which the processing times of the jobs follow different distributions. We test three weight scenarios: the weights and processing times of the jobs are positively, negatively, and randomly correlated. For all the testing problems, WVS and WSS methods are able to produce smaller WWTV than FIFO and WSPT. WVS outperforms WSS in the PW and RW scenarios while WSS can further reduce WWTV than WVS under NW weight scenario for Pareto and exponentially distributed testing problems. WSS can be applied to job scheduling on computer and network resources due to its computational efficiency and comparable performance to that of WVS. There are wide applications of WSS and WVS to schedule jobs to receive services from computer and network resources for providing QoS stability and performance dependability for jobs requesting services. For instance, WSS and WVS algorithms can be applied to a router to reduce the weighted waiting time variance of the data packets, a web server to schedule the web requests, and so on. Although we develop WVS and WSS in the context of Quality of Service on computers and networks, these job scheduling methods for service stability are also applicable to job scheduling problems in many other application fields that demand for service stability and performance dependability. For example, WVS and WSS can be applied to manufacturing production planning for scheduling jobs in a batch on a manufacturing machine. Further research can be undertaken to investigate Pm∥WWTV and Qm∥WWTV problems in which multiple machines are involved. It is of interest to find out whether the nondelay property of the optimal sequence of 1∥WWTV still holds under multiple machine environment and to develop fast algorithms for Pm∥WWTV and Qm∥WWTV.