Deterministic Heuristics for an Integrated Optimization Problem with Job Outsourcing Options and Single-machine Batch Scheduling
The integrated optimization problem of job outsourcing and scheduling on a single batch-processing machine was studied from the manufacturers'perspective.A 0-1 programming model was established with the objective of minimizing the sum of the total job outsourcing cost and total in-house batch processing cost,while both nondeterministic polynomial(NP)hardness and optimality properties were analyzed.Two deterministic heuristics in polynomial complexity were proposed by two different ways of determining the set of outsourcing jobs and their respective appropriate groups of job filtering orders.They were job addition heuristic(JAH)and job removal heuristic(JRH).In the simulation experiments,performance of both JAH and JRH algorithms in solution quality and running time was comparatively analyzed over plenty of problem instances.Experimental results show that the two heuristics are both capable of obtaining high-quality near solutions in a short time,and JRH indeed significantly outperforms JAH in terms of optimization quality by comparison.
NETL
NSTL
万方数据
