A double-layered optimisation approach for the integrated due date assignment and scheduling problem

Abstract

As the market competition becomes fiercer, contemporary make-to-order firms are confronted with both due date quotation and production scheduling problems at the same time. On the one hand, in order to attract customers, the firm needs to quote a short lead time; on the other hand, once a due date has been promised, the firm must spare no effort to deliver the goods no later than this date. If due date assignment and shop scheduling are processed separately by two systems, the overall performance is unlikely to be satisfactory because the two tasks are actually interrelated (e.g. a tighter due date setting will increase the chances of tardiness despite its appeal for the incoming customer). Therefore, we consider the problem by integrating due date assignment and shop scheduling into one optimisation model. A double-layered heuristic optimisation algorithm is presented for solving this problem. In the upper-layer genetic algorithm which performs coarse-granularity optimisation, Bayesian networks are used to learn the distribution of optimal due date values. As the second-layer algorithm, a parameter perturbation method is applied for a finer-granularity neighbourhood search. Computational experiments prove the efficacy and efficiency of the proposed algorithm.

Keywords:

• due date assignment
• job shop scheduling problem
• estimation of distribution
• parameter perturbation method

Acknowledgements

The authors express their sincere thanks to the anonymous reviewers for their helpful comments and Prof Chiang for his kind assistance. This article was supported by the National Natural Science Foundation of China (Nos. 60874071, 71001048).

Notes

Notes

1. In a Bayesian network, if there exists a directed arc pointing from node X _j to X _i , then X _j is called a parent of X _i .

2. TWT-JSSP is strongly 𝒩𝒫-hard because J//∑w _j T _j is a generalisation of the single-machine problem 1//∑w _j T _j , which has been proven to be strongly 𝒩𝒫-hard in (Lawler 1977, Lenstra et al. 1977).