Scheduling linearly deteriorating jobs by two agents to minimize the weighted sum of two criteria
Introduction
Agent scheduling is a new research area in modern scheduling theory, initiated by Agnetis et al. [3] and Baker and Smith [5]. As opposed to classical scheduling, where jobs are processed on machines used in a centralized way, agent scheduling jobs are processed on machines utilized by two or more competing agents. Moreover, the agents have their own optimality criteria, while in classical scheduling only one criterion is used. These two assumptions allow us to construct more realistic models of modern manufacturing processes in which competitiveness plays an important role.
Though agent scheduling is intensively studied recently, results of the research concern mainly problems with fixed job processing times that do not change in time. We refer the reader to papers by Agnetis et al. [4] and Tuong et al. [19] for reviews of this part of agent scheduling literature, and to monograph by Agnetis et al. [1, Chapter 3–5] for detailed discussion of the subject.
In this paper, we consider a two-agent scheduling problem in which jobs have variable processing times that deteriorate, i.e., the processing time of each job is a non-decreasing function of the starting time of the job. The contribution of the paper is three-fold. First, we present a detailed analysis of the problem, proving its and several properties that describe the structure of schedules for the problem. Second, we propose for our problem an exact algorithm and a meta-heuristic, both written in a modern object-oriented programming language. Finally, we report the results of computational experiments that we have conducted in order to evaluate the quality of schedules generated by our algorithms.
The problem under consideration can be formulated as follows. We are given a set of independent jobs that are available for processing at time . The set is divided into two subsets and such that , , and , where . Any job from the set is characterized by processing time and weight , where . Any job from the set is characterized by processing time and due-date , where . The processing time of job of agent , is a linear function of the starting time of the job, i.e. for , where , and denote the basic processing time, the deterioration rate and the starting time of the job, respectively. Jobs from the set are scheduled by agent Ak that has the optimality criterion fk, , where and . The aim is to find such a schedule σ that minimizes the criterion , where and denote the weight and the completion time of the jth job in schedule σ, respectively, and is a given constant. Throughout the paper, we denote the above problem as .
Despite the fact that scheduling problems with deteriorating processing times of jobs are very common in some applications (see, e.g., [8, Section 5.4] for a review), only a few authors have considered agent scheduling problems of this type, studying mainly polynomially solvable cases or proposing heuristic algorithms for known cases of such problems. Liu and Tang [15] have shown that single machine problems with proportional job processing times, and , can be solved in and time, respectively. Liu et al. [16] generalized the results to a single machine batch scheduling environment, and Liu et al. [14] extended them to proportional-linear processing times, . Lee et al. [12] proposed a branch-and-bound algorithm for a two-agent single-machine scheduling problem with linear job processing times, , and criteria and , where if and otherwise. Gawiejnowicz et al. [9] proposed a branch-and-bound algorithm and a meta-heuristic for a single machine problem with proportional job processing times and the total tardiness and the number of tardy jobs criteria, .
Agent scheduling problems with other forms of variable job processing times have been considered, e.g., by Wan et al. [20], Cheng et al. [7], Li and Hsu [13] and Wu et al. [21]. We refer the reader to [1, Chapter 6] for detailed discussion of agent scheduling problems with variable job processing times.
This paper is organized as follows. In Section 2 we prove that problem is regardless of or not. In Section 3 we prove several basic properties of the problem in the case when aj=0. In Sections 4 and 5 we present for the latter case an exact algorithm and a meta-heuristic algorithm, respectively. Results of an experimental evaluation of both these algorithms are reported in Section 6. We complete the paper in Section 7 including conclusions and remarks on further research.
Section snippets
Complexity of problem
In this section, we show that the considered problem is computationally difficult. The problem with linear job processing times, with for , includes the strongly scheduling problem with fixed job processing times, , considered by Baker and Smith [5]. Therefore, problem is strongly as well.
In view of this, in the remaining sections of the paper we focus on the case when aj=0 for and .
If , i.e. when
Properties of problem
In this section, we present several properties that allow us to describe the structure of schedules for problem and play an important role in the exact algorithm presented in Section 4.
Throughout this section, unless stated otherwise, we apply the following notation. For brevity, if this does not lead to ambiguity, we drop symbol Ak and write and dj instead of and , respectively. Given a schedule for the problem, a subset of jobs and jobs
Exact algorithm for problem
In this section, we present the exact algorithm for the considered problem. We use the algorithm as a tool of comparison of the relative power of properties considered in Section 3 and in the evaluation of the quality of schedules generated by the meta-heuristic presented in Section 5.
Meta-heuristic for problem
In this section, we present a meta-heuristic algorithm for our problem.
Computational experiments
In this section, we describe the results of computational experiments that we have conducted in order to verify the quality of schedules generated by the algorithms described in 4 Exact algorithm for problem, 5 Meta-heuristic for problem.
Conclusions
We considered a two-agent single machine problem of scheduling linearly deteriorating jobs with non-zero weights and due-dates. The objective was to minimize a weighted sum of the total weighted completion time and the maximum lateness criteria. We have shown that the problem is regardless the basic job processing times are equal to zero or not. We also proved several properties describing the structure of sub-optimal and optimal schedules for the considered problem, and proposed an
Acknowledgments
The research of Dr. Gawiejnowicz has been supported by National Science Center Grant no. N519 643340.
References (21)
- et al.
Two-agent scheduling with position-based deteriorating jobs and learning effect
Appl Math Comput
(2011) - et al.
A single-machine scheduling problem with two-agent and deteriorating jobs
Appl Math Model
(2010) - et al.
Solving a two-agent single-machine scheduling problem considering learning effect
Comput Oper Res
(2012) - et al.
Two-agent single-machine scheduling problems under increasing linear deterioration
Appl Math Model
(2011) Scheduling jobs under simple linear deterioration
Comput Oper Res
(1994)- et al.
“Product Partition” and related problems of scheduling and systems reliabilitycomputational complexity and approximation
Eur J Oper Res
(2010) - et al.
Scheduling two agents with controllable processing times
Eur J Oper Res
(2010) - Agnetis A, Billaut J-C, Gawiejnowicz S, Pacciarelli D, Soukhal A. Multiagent scheduling: models and algorithms. Berlin,...
- et al.
Sequencing unreliable jobs on parallel machines
J Sched
(2009) - et al.
Scheduling problems with two competing agents
Oper Res
(2004)