BI-CRITERIA SINGLE MACHINE BATCH SCHEDULING WITH BOUNDED BATCH AND JOB FAMILIES

摘要

This paper introduces a multi-family integrated batching and scheduling problem with upper bounded batches, sequence-independent setup times, item availability, and unrestricted sizes and processing times of jobs. The problem is a combination of multi-family one-dimensional Bin Packing Problem and Single Machine Scheduling Problem. This type of problem can be found in, for example, steel roof tiles production process. Mixed integer programming model of the problem is provided and two simple heuristics are proposed to solve it. The heuristics are evaluated using a set of benchmarks, based on real-life data and compared with the results obtained by CPLEX solver. The two developed heuristics, based on NEH and Batch First Fit algorithm, achieve better results than the CPLEX solver. Additionally, the results are provided for weighted combination of tardiness and batches fulfilment. In some applications both tardiness and earliness should be considered as the objective function. In some cases, scheduled orders and their deliveries should be closely agreed, as delivery cost can be very significant. Using various weights a planner can control the impact of those two criteria on the final solution. The paper presents an original practical problem that can be found in some real production processes, filling the gap in the scheduling literature in this respect.