Heuristics and lower bound for minimizing maximum lateness on a batch processing machine with incompatible job families. (June 2019)

• Record Type: Journal Article
• Authors: Li, XiaoLin; Li, YuPeng; Huang, YanLi
• Is Part Of: Computers & operations research. Volume 106(2019)
• Page Start: 91
• Page End: 101
• Publication Date: 2019-06
• Subjects: Batch processing machine -- Heuristics -- Maximum lateness -- Lower bound -- Job families; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.02.012
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The problem of scheduling non-identical jobs from in-compatible families on a batch processing machine to minimize maximum lateness is studied and the mathematical model is presented. Lower bound algorithm for the problem under study is designed based on the lower and upper bound of batch number. Heuristics based on LPT and EDD rules are designed and improved by optimizing critical batch. Abstract: Production efficiency can be greatly improved by using batch processing machines which can process several jobs in parallel. When job processing characteristics are different, job family should be further considered to group jobs properly in a batch. The problem of scheduling non-identical jobs from incompatible job families on a batch processing machine is investigated in this paper. Job sizes are non-identical and the objective is to minimize the maximum lateness Lmax . Batch processing time is determined by the job with the longest processing time and batch due date equals to the earliest job due date in the batch. Only jobs from the same job family can be grouped together in the same batch. A mathematical model of the problem under study is formulated and validated by using CPLEX. A lower bound is proposed based on the lower bound and the upper bound of the batch number. Because of the NP-hardness of the problem, heuristics are designed to solve the problem under study. These heuristics are then improved by optimizing completion time or due date of the critical batch. Experimental studies show that heuristics could be effectively improved by CTD (Completion Time Decreasing) rules.