This paper deals with the issue of economic batch quantity (EBQ) in a single machine system in which defective items are produced in each cycle of production. The accumulated defective items produced in a period, cons...
详细信息
ISBN:
(纸本)9781424435395
This paper deals with the issue of economic batch quantity (EBQ) in a single machine system in which defective items are produced in each cycle of production. The accumulated defective items produced in a period, consisting of several equal cycles, are all reworked in the last cycle of this period called the rework cycle. At the end of each period the whole process will start all over again. We assume that there is a limitation on the total defective items. We also do not adopt the restriction that the rework process rate be equal to the normal production rate. In addition we assume that there is a set up time for rework process. Further we assume that the number of rework cycles be as small as possible, which is mainly due to changeover costs needed for going from normal production to rework as well as special attention required for rework to satisfy the zero defect criterion. Finally, for the ease of production and resource planning, the rework cycle has to have the same length as the other cycles. For this system, assuming no shortages are permitted we obtain the economic batch quantity which minimizes the total cost of the system.
Recent papers have proposed to design scheduling algorithms entirely as discrete-time controllers, i.e., to refrain from preserving the already installed scheduler, and replace it completely. At the cost of some syste...
详细信息
ISBN:
(纸本)9781467345057
Recent papers have proposed to design scheduling algorithms entirely as discrete-time controllers, i.e., to refrain from preserving the already installed scheduler, and replace it completely. At the cost of some system re-design impact, this new approach has been proved to yield significant advantages in terms of code size and simplicity, and above all to open the way to a system-theoretical analysis, thereby permitting to prove relevant properties in a rigorous manner. This manuscript presents some refinements and improvements of an already conceived control structure, allowing for more flexible task management and better comprehension on the part of the system administrator. A standard benchmark is used to support the necessary performance analysis.
We study a methodology for constructing scheduled systems by restricting successively the behavior of the processes to be scheduled. Restriction is used to guarantee the satisfaction of two types of constraints: sched...
详细信息
ISBN:
(纸本)3540410554
We study a methodology for constructing scheduled systems by restricting successively the behavior of the processes to be scheduled. Restriction is used to guarantee the satisfaction of two types of constraints: schedulability constraints characterizing timing properties of the processes, and constraints characterizing particular scheduling algorithms including process priorities, non-idling, and preemption. The methodology is based on a controller synthesis paradigm. The main results deal with the characterization of scheduling policies as safety constraints and the simplification of the synthesis process by applying a composability principle.
Optical fiber networks provide huge bandwidth to accommodate the rapid growth of Internet traffic. Due to bursty nature of the Internet traffic, optical burst switching (OBS) is highly suitable for metropolitan area n...
详细信息
ISBN:
(纸本)9781467359979;9781467359993
Optical fiber networks provide huge bandwidth to accommodate the rapid growth of Internet traffic. Due to bursty nature of the Internet traffic, optical burst switching (OBS) is highly suitable for metropolitan area networks compared to circuit switching. This paper devises and presents three new scheduling algorithms for OBS based metropolitan area networks capable of providing quality of service (QoS) to delay sensitive applications. Specifically, these algorithms are able to provide differentiated service to voice, video and data traffic according to their acceptable performance metrics. Detailed simulation experiments are presented which were used to study the performance and to validate the effectiveness of the proposed scheduling algorithms with augmented QoS capabilities over a ring OBS network.
For a time-sensitive application, the usefulness or the quality of the application's end result depends on the time when the result is delivered, or when the application is completed. A Time Utility Function (TUF)...
详细信息
ISBN:
(纸本)9781479975754
For a time-sensitive application, the usefulness or the quality of the application's end result depends on the time when the result is delivered, or when the application is completed. A Time Utility Function (TUF) is often used to represent the dependency between an application's accrued value and its completion time. For parallel and time-sensitive applications, each application has multiple tasks that must be executed concurrently in order to produce a result. Therefore, their execution occupies resources in two dimensions: spatial, i.e., the number of processing units needed to support concurrent tasks, and temporal, i.e., time duration needed to complete the application. Because of the parallelism and time-sensitive features of the applications, the execution interference among parallel and time-sensitive applications can be both in spatial and temporal domains. In this paper, we first introduce a metric to measure the spatial-temporal interference on applications' accrued values. Second, based on the metric, we develop a scheduling algorithm, i.e., the Discounting Spatial-Temporal Interference (DSTI) scheduling algorithm, to maximize system's total accrued utility value for a given set of parallel and time-sensitive applications. Our simulation results show that the proposed DSTI algorithm results in close to optimal solutions and also has clear advantage over existing approaches in the literature in terms of system total accrued utility values and profitable application ratio. It accrues up to 164%, 150%, and 97% more system value, and up to 21%, 35%, and 18% higher profitable application ratio than the Gang EDF, the FCFS with backfilling, and the 0-1 Knapsack based scheduling algorithms, respectively.
Run-time reconfigurable computing extends the classic role of FPGAs towards processing elements which feature multitasking similar to a micro processor. The main advantage of this usage is based on the granularity of ...
详细信息
ISBN:
(纸本)9781424421091
Run-time reconfigurable computing extends the classic role of FPGAs towards processing elements which feature multitasking similar to a micro processor. The main advantage of this usage is based on the granularity of the reprogrammable device which can be optimally adapted to each task that has to be executed. Hence, scheduling for such a usage scenario becomes apparent, where a set of tasks with their specific area demands and execution time has to be executed. Obviously, the provision of a set of design alternatives for each task will allow for a higher utilization of the FPGA. Nevertheless, it is computational impossible to facilitate all the theoretically achievable design alternatives of one task. Thus, this paper presents an scheduling algorithm that reduces the number of design alternatives that are utilized for a schedule. Furthermore, a scheduling algorithm is presented which achieves optimization in feasible execution time.
Motivated to design a feasible optical network architecture for the future Internet, we address the question of scheduling (wavelength assignment) in an optical network. The key challenge in designing a scheduling alg...
详细信息
ISBN:
(纸本)9781424422463
Motivated to design a feasible optical network architecture for the future Internet, we address the question of scheduling (wavelength assignment) in an optical network. The key challenge in designing a scheduling algorithm lies in solving a combinatorial optimization problem under very stringent distributed constraints. Specifically, given R random variables x(1),..., x(R) taking integer values, each variable is required to find its assignment so that collectively they maximize Sigma(r) W(r)x(r) subject to some linear constraints that Ax <= C. In doing so, each variable can only avail of two pieces of information (and nothing else): one, its own weight W-r, two, given its current values (and the values of other variables being unknown), can it increase it by +1 or not. As the main result of this paper, we present a randomized algorithm that solves this problem. Our algorithm builds upon classical theory of reversible networks. To the best of our knowledge, this is the First such algorithm for such a stringent distributed problem.
We consider the problem of minimizing the time average cost of sampling and transmitting status updates by users over a wireless channel subject to average Age of Information constraints (AoI). Errors in the transmiss...
详细信息
ISBN:
(纸本)9781728186955
We consider the problem of minimizing the time average cost of sampling and transmitting status updates by users over a wireless channel subject to average Age of Information constraints (AoI). Errors in the transmission may occur and the scheduling algorithm has to decide if the users sample a new packet or attempt for retransmission of the packet sampled previously. The cost consists of both sampling and transmission costs. The sampling of a new packet after a failure imposes an additional cost in the system. We formulate a stochastic optimization problem with time average cost in the objective under time average AoI constraints. To solve this problem, we apply tools from Lyapunov optimization theory and develop a dynamic algorithm that takes decisions in a slot-by-slot basis. The algorithm decides if a user: a) samples a new packet, b) transmits the old one, c) remains silent. We provide optimality guarantees of the algorithm and study its performance in terms of time average cost and AoI through simulation results.
As cloud services grow to span more and more globally distributed datacenters, there is an increasingly need for scheduling algorithms to automatically place tasks across these datacenters. In geo-distributed cloud, t...
详细信息
ISBN:
(纸本)9781509036530
As cloud services grow to span more and more globally distributed datacenters, there is an increasingly need for scheduling algorithms to automatically place tasks across these datacenters. In geo-distributed cloud, the limited WAN bandwidth has become the major bottleneck in fast big data analytics. The scheduling algorithm needs to minimize the global completion time, by jointly optimizing task scheduling and WAN data transfer. In this paper, we model the task scheduling as a community detection problem, with respect to the dependency relations between task, data, and datacenters, and propose a Community Detection-based scheduling (CDS) algorithm, which is able to minimize the WAN data transfer volume. We utilize the real China-Astronomy-Cloud network to evaluate the proposed algorithms. Experimental results show that we can reduce the total data transfer volume by up to 40.7%, and the global completion time by up to 35.8%, compared with the Hypergraph Partition-based scheduling algorithm and the greedy scheduling algorithm.
Generalized Processor Sharing (GPS), which provides the theoretical underpinnings for fair packet scheduling algorithms, has been studied extensively. However, a tight formulation of the available service to a flow on...
详细信息
ISBN:
(纸本)9780988304567
Generalized Processor Sharing (GPS), which provides the theoretical underpinnings for fair packet scheduling algorithms, has been studied extensively. However, a tight formulation of the available service to a flow only exists for traffic that is regulated by affine arrival envelopes and a constant-rate link. In this paper, we show that the universal service curve by Parekh and Gallager can be extended to concave arrival envelopes and links with time-variable capacity. We also dispense with the previously existing assumption of a stable system.
暂无评论