In the cost minimization problem, the set of jobs to be processed is given, and the goal is to schedule all jobs within a planning horizon so as to minimize the total cost, while in the profit maximization problem, one needs to select a set of jobs to be processed such that the total profit is maximized.
The general cases of the cost minimization and profit maximization problems in which preemptions are forbidden are strongly NP-hard. In this paper, we show that some special cases with identical processing times can be solved by efficient algorithms. In addition, we consider several extensions of the problems, including release times, due dates, and variable energy consumption.
Introduction and literature review Recently, many manufacturing and energy companies have shown an increased interest in sustainable scheduling.
This interest has led to the implementation of variable pricing to manage the balance between supply and demand for electricity and to improve the reliability and efficiency of electrical power grids.
For example, with time-of-use TOU tariffs, retail energy prices to customers vary hourly to reflect changes in wholesale energy prices. Such price structures are used to shift energy-intensive production jobs from peak hours to off-peak hours and to significantly reduce costs. Gahm et al. They further develop a research framework for EES scheduling and provide an empirical analysis of the reviewed literature and emphasize the benefits that can be achieved by EES in practice.
Among these is the work of Wan and Qi , who study scheduling under operational costs that vary over time. They prove the intractability of the models under general parameters and provide polynomial-time algorithms for special cases with nonincreasing time slot costs.
Zhong and Liu consider a single-machine scheduling problem in which processing of a job incurs a cost that depends on the time slots occupied by the job. Their objective is to minimize a linear combination of the makespan and the total time slot costs.
They prove that the problem is strongly NP-hard and analyze a special case with nonincreasing time slot costs. Zhao et al. Focusing on the case of nonincreasing time slot cost with nonpreemptive jobs, they show that the problem can be solved in polynomial time when the time slot cost decreases with certain patterns and is NP-hard in the general decreasing-patterns case.
Shrouf et al. The authors present a genetic algorithm heuristic for this problem. Che et al investigate a single-machine scheduling problem under TOU tariffs to minimize the total electricity cost. A continuous-time MILP model is developed, and an efficient greedy insertion heuristic is proposed. Che et al address a single-machine scheduling problem with a power-down mechanism to minimize total energy consumption and maximize tardiness simultaneously. A MILP model based on position assignment has been developed to formulate the problem.
Fang et al. They study two variations of the problem: the uniform-speed case, in which all jobs have given processing times, and the speed-scalable case, in which the planner can control the processing speed and thus the processing time of each job. In the uniform-speed case, the energy consumption of each job is given and is not necessarily proportional to the processing time.
On the other hand, for a special case of the problem, i. Rubaiee et al. They formulate the problem as a mixed-integer multiobjective mathematical programming model and develop four multiobjective genetic algorithms to obtain a near-optimal Pareto front in a timely fashion. Each job has its own processing time and energy consumption. The machine may switch among three different states. The aim is to minimize the total energy consumption costs. The authors suggest a dynamic programming approach to model the problem.
They use the Dijkstra algorithm to calculate a shortest path on a finite graph. Using this approach, the authors show that the uniform speed case of this problem is solvable in polynomial time. In addition, if the order of the jobs is not predefined, the authors provide a polynomial-time algorithm for constant, increasing, or decreasing energy costs.
They use the 3-partition problem to show that the case with non- predefined job order and TOU tariffs is NP-hard. Chen and Zhang consider the problem of scheduling jobs on a single machine to minimize the total electricity cost of processing these jobs under TOU electricity tariffs.
Under the very restricted condition of at most one valley, the authors show that the STOUC problem with either bounded lateness, bounded tardiness, or bounded flow-time is solvable in polynomial time. Since the energy cost minimization problem is NP-hard Fang et al. We took a different approach by allowing any cost resp. In this paper, we consider two variants of the single-machine scheduling problem with TOU tariffs: cost minimization and profit maximization.
To the best of our knowledge, we are the first to study the more challenging profit maximization problem. More specifically, in the cost minimization problem, the set of jobs to be processed is given, and the goal is to schedule all jobs within a planning horizon in a way that minimizes the total cost.
In the profit maximization problem, one needs to simultaneously select a subset of jobs to be processed and schedule them so that the total profit is maximized. We develop efficient algorithms for some variants of the problems with identical processing times as well as for preemptive versions of the problems.
In particular, for the nonpreemptive case with identical processing times, we develop a strongly polynomial 3-step algorithm for both the cost-minimization and profit-maximization objectives.
The first step of these algorithms is based on a greedy algorithm for the preemptive case, the second step uses dynamic programming that is applied to an instance of the problem with smaller dimension, and the third step merges the two solutions from the previous steps into a solution to the original problem.
For the cost minimization problem, we further develop a polynomial-time algorithm for the preemptive case with release times and due dates. Our algorithm is based on a reduction to the Hitchcock transportation problem.
In addition, we present elegant and compact integer programming formulations that capture many variants of the nonpreemptive unit time problems, including time-varying electricity tariffs, release times, and due dates for both the minimum cost and the maximum profit objectives. The rest of the paper is organized as follows: in Section 2, we introduce notations, define the problem variants formally and make some observations regarding the structure of an optimal solution.
In Section 3, we present polynomial-time algorithms for the unit-time nonpreemptive cost-minimization problem. In Section 4, the profit-maximization problem is analyzed.
The negative complexity result for the general case is presented as well as the polynomial-time algorithms for the preemptive and unit-time cases. In Section 5, we present a generalization of the cost minimization problems where release time and due dates are considered. In Section 6, we present integer programming formulations for an extension of problems in which the power consumption as well as other characteristics of each job may be different.
A summary of the results obtained in this paper and some final thoughts and directions for future study are presented in Section 7. Problem definitions and preliminaries 2. We consider the uniform-speed processing time where the production process consumes electrical energy at a constant rate and the electricity cost varies over time.
If the processing extends over several ETIs, the energy cost is calculated proportionally to the processing time during each ETI. We consider below two objective functions: minimum cost and maximum profit. We note that throughout the paper, we assume that the processing times of the jobs are positive integers and that all the other parameters are positive rational numbers. In addition, we assume that preemptions have no effect on the total processing times and processing costs of the jobs.
The jobs' revenues are irrelevant and thus ignored. We call the cost minimization problem identical if all processing times are identical. We consider four variants of the cost minimization problem.
In the identical case, we similarly differentiate between disallowing resp. For a given schedule, the profit is defined as the total job revenues minus the total energy cost.
We note that the additional degree of freedom resulting from the need to choose a subset of jobs to be processed leads to a more intricate problem, as indicated by our complexity analysis. We consider several variants of the profit maximization problem. In particular, we distinguish between identical processing times identical revenues , i. Note that no generality is lost by assuming unit processing times unit revenues in the identical cases since the lengths of the ETIs electricity tariffs are rational numbers.
That is, we have eight variants of the profit maximization problem since we have three binary properties that distinguish among them. For a given solution of a single-machine scheduling problem a busy period is a maximal time interval in which jobs are processed continuously on the machine.
We assume that switching between busy and idle periods does not incur any extra time or extra cost. Definition 2: The verge property. We say that a feasible solution of the cost minimization or profit maximization problem satisfies the verge property if each busy period starts at the beginning of an ETI or ends at the end of an ETI.
We note that the verge property plays an important role in the development of our algorithms. Proposition 1: There exist optimal solutions for the cost minimization and for the profit maximization problems having the verge property. This proposition, using different terminology, was proved independently by Chen and Zhang for the cost minimization version of the problem.
The proof for the maximum profit version is very similar and thus the it is omitted. The first starts resp. There are infinitely many other optimal solutions that do not satisfy the verge property. See Figure 3. Corollary 1 below is an immediate consequence of Proposition 1. It allows a solution of the identical-jobs variants in polynomial space to be described in terms of the number of ETIs. Since the complexity of an algorithm is calculated relative to the size of the input, we assume that the most compact possible representation is used for each variant of the problem.
Similarly, the complexity of an optimization algorithm can be affected by the representation of the output. In the 1 energy cost and 1 energy profit problems, a solution of a single-machine scheduling problem consists of a list of the scheduled tasks and their respective starting times. Therefore, with this output representation, it may be possible to develop a strongly polynomial-time algorithm for some identical jobs cases.
In Table 1, we list the variants of the problem in this study along with their input and output representation schemes and the size of these representations using O-notation. The cost minimization problem. The first step of this algorithm is based on a greedy algorithm for the preemptive case, the second step uses a dynamic program, and the third step merges the two solutions from the previous steps into a list of busy periods.
The following proposition is an adaptation of a result by Fang et al Proof: Recall that the solution of this variant is a list of busy periods. The problem is solved by a greedy procedure that first calculates the total required processing time and then allocates processing times to the cheapest ETIs.
The procedure requires sorting the ETIs in nondecreasing order of cost and then allocating the processing times of all the jobs to the ETIs one by one. Note that if the jobs are identical, i. In this case, the time complexity is O K log K.
Observe that a lower bound on the value of the optimal solution is provided by the value of the optimal solution when preemptions are allowed. The idea is to schedule many of the unit-time jobs in ETIs according to the solution of the preemptive case.
Finally, the two solutions are combined. This problem is solved by a dynamic programming algorithm described below: Recall that by Proposition 1, there exists an optimal solution for the streamlined problem that satisfies the verge property, i. For the identical-processing-time case, this solution implies that the other end of a busy period the one that does not necessarily coincide with an ETI verge must be at an integer time difference from such a verge.
In addition, for each candidate starting point, we can calculate the total energy cost of processing a job starting at this point. Solve this problem using the dynamic programming algorithm described above.
When applying Algorithm 1, we first solve the problem with preemptions. See Figure 4. The optimal solution at this step obtained by solving the above dynamic program when represented as the time allocated at each ETI is 1. Nine jobs are processed from time 0 to time 9 and eleven from time 13 to time Clearly, this outcome occurs because adding additional jobs at time 9 will require the allocation of processing time at the third ETI, which is very costly.
Proof: We first prove the feasibility of the obtained solution. That is, we show that the time allocated by Step 3 satisfies the following requirements: 1. Note that by definition, a busy period does not contain idle time. For example, the vector 0. Constraint 4 stipulates that we allocate enough time to process all the jobs. Constraint 5 limits the allocation of times to ETIs in such a way that allows them to be arranged into busy periods of integer length.
This busy period was created by adding integer times allocated at Step 1 to the busy period also of integer length created at Step 2. Clearly, the sum of several integers is also an integer. Next, we prove the optimality of the solution. Such an optimal solution exists by Lemma 1. Finally, if the lengths of the ETIs are all integers, preemption will not occur in the optimal schedule obtained from the greedy procedure since jobs have a unit size, and all events happen at integral times.
Therefore, it is possible to use the same greedy procedure that solves the preemptive case to solve the non-preemptive one.
The profit maximization problem We turn now to the maximum-profit version of the scheduling problem under TOU electricity tariffs. In Section 4. In the remainder of Section 4, we continue to the more intricate cases in which preemptions are not allowed. Otherwise, if in an optimal solution of the profit maximization problem some jobs are not scheduled the cost minimization problem admits no feasible solution. Proof: The proof is accomplished by a reduction of the NP-complete decision problem "subset sum" Karp The time complexity and the space complexity.
The time complexity is defined as the process of determining a formula for total time required towards the execution of that algorithm. This calculation is totally independent of implementation and programming language. Space complexity is defining as the process of defining a formula for prediction of how much memory space is required for the successful execution of the algorithm.
The memory space is generally considered as the primary memory. Monica Mona. Previous Page Print Page. Next Page.
0コメント