Minimizing the Number of Tardy Jobs in the Single Machine Scheduling Problem under Bimodal Flexible and Periodic Availability Constraints

In singl machin e scheduli ng problems with availability constraints, machine s are not av ailable for one or mor e periods o f time. In this paper, a single machine sc heduling p roblem with flexible an d periodic availability constraint s is investig ated. In this problem, the maxim um continuous working time for e ach machine can increase in a s tepwise manner and can have two differen t values. In addition, the duratio of unavai lability for each period depends on the maxi mum contin uous working time of the machine in that sa me period, again with two differe nt values. The objective is to min imize the n umber of tardy jobs. In the firs t stage, the complexit y of the pr oblem is in vestigated; then, a bin ary integer programm ing model , a heuristic algorithm , and a branch-and - bound algorithm are proposed in the second stage. Computationa l results of solving 16 80 sample problems in dicate that the branch - and-boun d algorithm is capable of not only solving pr oblems up to 20 jobs, but also of optimally s olving 94.76% of the total number of proble ms. Based o n the comp utational r esults, a mean average error of 2% is obtained for the heuristic algorithm

کلیدواژه ها:

single machine ، flexible periodic availability constraints ، bimodal ، tardy jobs ، branch-and-bound