Research On Earliness-tardiness Scheduling Problem On A Batch Machine With Non-identical Job Sizes And A Common Due Date

Batch scheduling problem is a typical modern scheduling problem widely applied in industrial production environments like semiconductor manufacturing, transportation, production management and so on. A wide range of application of JIT principle in industrial production brings batch scheduling research a new issue, namely minimization problem for total earliness and tardiness of all jobs. As earliness would result in a holding cost while tardiness may lead to customer dissatisfaction. E/T(Earliness/tardiness) related research would have a direct impact on customer delivery and cost performance so that it is valuable to study this problem for both theory and economic benefit.This paper considers the scheduling problem with objective of minimizing earliness-tardiness (E/T). Firstly, related background and problem description are introduced systematically. A comprehensive review is made for related batch scheduling research. Then E/T batch scheduling problems are described in detail and examples are given.A specific E/T batch scheduling problem of minimizing E/T on a single batch processing machine with a common due date is studied. First, a mathematical model is formulated. By introducing the concept of ARB(Attribute Ratio of Batch),several optimal properties of batching jobs are proven. Then a new heuristic algorithm for batching and a hybrid genetic algorithm are proposed. Computational experiments are carried out to test the performance of the algorithms.To make the research more practical, penalty of tardiness is introduced in the study. A mathematical model for E/T scheduling problem with constraint of tardiness penalty is formulated. Several optimal properties are proven and three heuristics are developed based on the different heuristic information. Meanwhile, genetic algorithm is applied on this problem. Four different categories of due date and tardiness penalty are designed in the computational experiments to analyze how due date and tardiness penalty affect performance of both heuristics and genetic algorithm.Finally, we summarized the content of this article and gave the direction of further research.