A just-in-time scheduling problem with two competing agents
- PDF / 381,119 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 252 Views
A just-in-time scheduling problem with two competing agents Byung-Cheon Choi1 · Jibok Chung2 · Myoung-Ju Park3 Received: 3 September 2018 / Accepted: 10 October 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract We consider a single-machine scheduling problem with two competing agents. The objective is to minimize the total weighted completion time of jobs of agent 1 with a constraint on the total weight of the just-in-time jobs of agent 2. Our problem can be categorized into the non-preemptive and the preemptive versions, depending on whether the preemption is allowed for jobs of agent 1. First, we show that some open cases of the first version are NP-hard. Then, we categorize the second version into several cases, depending on whether the processing times or the weights of each agent are identical. We analyze how the computational complexity is affected by the identical processing times or the identical weights of each agent. Keywords Scheduling · Preemption · Competing agents · Just-in-time job · Complexity
1 Introduction We consider a two-agent single-machine scheduling problem. The objective is to minimize the total weighted completion time while the total weight of just-in-time
B
Myoung-Ju Park [email protected] Byung-Cheon Choi [email protected] Jibok Chung [email protected]
1
Department of Business Administration, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, Korea
2
Department of Industrial Channels Management, Kongju National University, 54 Daehak-ro, Yesan-eup, Yesan-gun, Chungcheongnam-do 32439, Korea
3
Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea
123
B.-C. Choi et al.
jobs for agent 2 is greater than or equal to a given threshold. A just-in-time (JIT) job is defined as a job that is completed exactly on its due date. Both agents have their own sets of jobs and share common resources (machines) for processing jobs with other agents. The problems are formally formulated as follows. Agent h, h = 1, 2 has a set of n h jobs J h = {J1h , J2h , ..., Jnhh } and each job J jh has a weight w hj and a processing time p hj . Each job J j2 of agent 2 has a due date d 2j . Let σ be a feasible schedule and C hj (σ ) the completion time of J jh in σ . Let E hj (σ ) be an indicator variable of J jh in σ , defined as E hj (σ )
=
1 0
ifJ jh is a JIT job, otherwise.
This paper considers a problem, referred to as Problem P: minimize
J j1 ∈J 1
w 1j C 1j (σ ) subject to
w 2j E 2j (σ ) ≥ λ,
J j2 ∈J 2
where λ is a given positive threshold. Without loss of generality, assume that • The preemption for jobs of agent 2 is not allowed. • The non-JIT jobs of agent 2 are rejected. • d12 ≤ d22 ≤ · · · ≤ dn22 . Our problem has two versions, preemptive and non-preemptive versions, depending on the preemption for jobs of agent 1. This is motivated in preventive maintenance (PM) planning under the following environments • A machine manager can select
Data Loading...
