  


Scheduling jobs with a Vshaped timedependent processing time
Helmut Sedding (helmutsedding.net) Abstract: In the field of timedependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are wellknown in the literature, this paper introduces nonmonotonic functions with a convex, piecewiselinear Vshape 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 jobspecific. 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 timedependent walking times to gather materials from the lineside is minimized. This paper characterizes the problem’s computational complexity in several angles. NPhardness 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 jobspecific slopes, several polynomial cases are identified. Keywords: Singlemachine scheduling; Timedependent scheduling; Nonmonotonic processing time; Piecewiselinear processing tim; Convex Vshaped processing time Category 1: Applications  OR and Management Sciences (Scheduling ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 02/01/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  