Scheduling linearly deteriorating jobs by two agents to minimize the weighted sum of two criteria

https://doi.org/10.1016/j.cor.2014.06.020Get rights and content

Abstract

We consider scheduling jobs by two agents on a single machine. Each job is defined by a common release date, a deteriorating processing time that is a linear function of the job starting time and a weight or a due-date. Every agent constructs a partial schedule that includes only the agent׳s jobs and is evaluated by the agent׳s optimality criterion: the total weighted completion time or the maximum lateness. The aim is to find a complete schedule minimizing a weighted sum of the two criteria. We prove that the problem is NP-hard and show several properties that describe the structure of schedules for the problem. We also propose an exact algorithm and a meta-heuristic for the problem. Finally, we report the results of evaluation of the proposed algorithms by computational experiments.

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 NP-hardness 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 J of independent jobs that are available for processing at time t0>0. The set J is divided into two subsets J1 and J2 such that J1J2=, J1J2=J, J1={J1A1,J2A1,,Jn1A1} and J2={J1A2,J2A2,,Jn2A2}, where n1+n2=n. Any job JjA1 from the set J1 is characterized by processing time pjA1 and weight wjA1, where 1jn1. Any job JjA2 from the set J2 is characterized by processing time pjA2 and due-date djA2, where 1jn2. The processing time pjAk of job JjAk of agent Ak,k{1,2}, is a linear function of the starting time of the job, i.e. pjAk=ajAk+bjAkSjAk for 1jni, where ajAk0, bjAk0 and SjAkt0 denote the basic processing time, the deterioration rate and the starting time of the job, respectively. Jobs from the set Jk are scheduled by agent Ak that has the optimality criterion fk, k{1,2}, where f1=A1wjCjJjA1wjCj and f2=LmaxA2maxJjA2{Cjdj}. The aim is to find such a schedule σ that minimizes the criterion f(σ)f1(σ)+θf2(σ)=A1wj(σ)Cj(σ)+θLmaxA2(σ), where wj(σ) and Cj(σ) denote the weight and the completion time of the jth job in schedule σ, respectively, and θ>0 is a given constant. Throughout the paper, we denote the above problem as 1|pj=aj+bjSj|A1wjCj+θLmaxA2.

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 NP-hard cases of such problems. Liu and Tang [15] have shown that single machine problems with proportional job processing times, 1|pj=bjSj|LmaxA1:CmaxA2U and 1|pj=bjSj|A1Cj:fmaxA2U, can be solved in O(n1logn1) and O(n1logn1+n2logn2) 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, pj=bj(a+bSj). Lee et al. [12] proposed a branch-and-bound algorithm for a two-agent single-machine scheduling problem with linear job processing times, pj=aj+bjSj, and criteria A1wjCj and A2Uj, where Uj1 if TjmaxjA2{Cjdj,0}>0 and Uj0 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, 1|pj=bjSj|A1Tj:A2Uj=0.

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 1|pj=aj+bjSj|A1wjCj+θLmaxA2 is NP-hard regardless of aj0 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 1|pj=aj+bjSj|A1wjCj+θLmaxA2

In this section, we show that the considered problem is computationally difficult. The problem with linear job processing times, pj=aj+bjSj with aj0 for 1jn, includes the strongly NP-hard scheduling problem with fixed job processing times, 1||A1wjCj+θLmaxA2, considered by Baker and Smith [5]. Therefore, problem 1|pj=aj+bjSj|A1wjCj+θLmaxA2 is strongly NP-hard as well.

In view of this, in the remaining sections of the paper we focus on the case when aj=0 for 1jn and θ=1.

If n2=1, i.e. when

Properties of problem 1|pj=bjSj|A1wjCj+LmaxA2

In this section, we present several properties that allow us to describe the structure of schedules for problem 1|pj=bjSj|A1wjCj+LmaxA2 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 pj,wj and dj instead of pjAk,wjAk and djAk, respectively. Given a schedule for the problem, a subset of jobs JkJk and jobs Jp,Jq

Exact algorithm for problem 1|pj=bjSj|A1wjCj+LmaxA2

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 1|pj=bjSj|A1wjCj+LmaxA2

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 NP-hard 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)

There are more references available in the full text version of this article.

Cited by (0)

View full text