Title :
Scheduling with fixed delivery dates and temporary storage
Author_Institution :
Dept. of Math. & Inf., Ludong Univ., Yantai, China
Abstract :
We considered the single machine scheduling with fixed delivery dates and temporary storage. The objective is to minimize the sum of the makespan and the total inventory costs. We showed that the problem is strongly NP-hard and polynomial-time approximation algorithm with a fixed performance ratio does not exist for the problem unless P=NP. A polynomial 3/2-approximation algorithm for the case with period delivery times was presented and the performance ratio of 3/2 can not be improved unless P=NP.
Keywords :
computational complexity; cost reduction; goods distribution; inventory management; minimisation; scheduling; storage; NP-hard; fixed delivery dates; makespan sum minimization; polynomial 3/2-approximation algorithm; polynomial-time approximation algorithm; single machine scheduling; temporary storage; total inventory costs minimization; Approximation algorithms; Costs; Economies of scale; Job shop scheduling; Mathematics; Polynomials; Postal services; Scheduling algorithm; Single machine scheduling; Supply chain management; Approximation Algorithm; NP-hardness; Performance ratio; Scheduling;
Conference_Titel :
Logistics Systems and Intelligent Management, 2010 International Conference on
Conference_Location :
Harbin
Print_ISBN :
978-1-4244-7331-1
DOI :
10.1109/ICLSIM.2010.5461283
