Scheduling jobs with a V-shaped time-dependent processing time
- PDF / 664,226 Bytes
- 18 Pages / 595.276 x 790.866 pts Page_size
- 11 Downloads / 184 Views
Scheduling jobs with a V-shaped time-dependent processing time Helmut A. Sedding1,2
© The Author(s) 2020
Abstract In the field of time-dependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are well-known in the literature, this paper introduces non-monotonic functions with a convex, piecewise-linear V-shape similar to the absolute value function. They are minimum at an ideal start time, which is the same for all given jobs. Then, the processing time equals the job’s basic processing time. Earlier or later, it increases linearly with slopes that can be asymmetric and job-specific. The objective is to sequence the given jobs on a single machine and minimize the makespan. This is motivated by production planning of moving car assembly lines, in particular, to sequence a worker’s assembly operations such that the time-dependent walking times to gather materials from the line-side is minimized. This paper characterizes the problem’s computational complexity in several angles. NP-hardness is observed even if the two slopes are the same for all jobs. A fully polynomial time approximation scheme is devised for the more generic case of agreeable ratios of basic processing time and slopes. In the most generic case with job-specific slopes, several polynomial cases are identified. Keywords Single-machine scheduling · Time-dependent scheduling · Non-monotonic processing time · Piecewise-linear processing time · V-shaped processing time
1 Introduction Sequencing a set of jobs on a single machine such that the makespan is minimized is trivial if each job’s processing time is constant, because any job sequence is optimal in this case. In contrast, if each job’s processing time is a function of its start time, then the job sequence alters the processing times. For example, if a swap of two jobs changes the sum of their processing times, then all succeeding jobs are shifted, which possibly necessitates a reoptimization. Hence, timedependent processing times add a layer of complexity, and already the makespan minimization poses a challenge.
penalty function j of start time t is added to the basic processing time j ≥ 0 of a job j to obtain the processing time p j (t) = j + j (t)
(1)
of job j. Then, the job is completed at C j (t) = t + p j (t).
(2)
1
Institute of Theoretical Computer Science, Ulm University, Ulm, Germany
Consequently, the completion time of a sequence of several jobs equals the composition of their completion time functions. For example, consider job sequence (1, 3, 2): If it is started at time t, then it completes at C2 (C3 (C1 (t))). Although existing literature studies many variations of j , they are largely restricted to monotonic, i.e., nondecreasing or nonincreasing forms (Gawiejnowicz 2008, 2020a, b; Strusevich and Rustogi 2017). A present practical case, arising in the context of moving assembly lines, requires a non-monotonic penalty function (Sedding 2020b), joining research lines on monotonic forms. In parti
Data Loading...
