کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
471696 | 698655 | 2011 | 20 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem with availability constraint](/preview/png/471696.png)
In this paper the problem of minimizing maximum earliness on a single machine with an unavailability period (1,h1∥Emax) and also the same problem with simultaneous minimization of the two criteria of maximum earliness and number of tardy jobs (1,h1∥Emax,NT) are studied. It is shown that the problem 1,h1∥Emax is NP-hard. For this problem a branch and bound approach is proposed which is based on a binary search tree. Proposing a heuristic algorithm named MMST, lower bound and efficient dominance rules, results in some instances with up to 3000 jobs being solved. The purpose in the problem 1,h1∥Emax,NT is to find the set of efficient solutions, i.e. the Pareto frontier. For this reason, for each measure Emax and NTNT at first changes domain are calculated. A heuristic algorithm named PH and a branch and bound approach are developed to solve the problem. Proposing a lower bound and some dominance rules resulted in 96.4% of instances being solved optimally which proves the efficiency of the proposed method.
Journal: Computers & Mathematics with Applications - Volume 62, Issue 9, November 2011, Pages 3622–3641