Single-Machine Scheduling (SMS) is an important problem which is NP-hard that is mainly studied in operations research and widely applied in several domains.
For our experiments, we have generated 48 SMS problem instances with different tardy factors and range factors using similar settings as given in Reference-1 below.
These benchmarks along with the best known solutions and the best known lower bounds obtained using one of the below algorithms can be downloaded by CLICKING HERE.
The procedure used for generating the instances is as follows:
Each instance contains 100 jobs.
For each job, an integer processing time, earliness penalty, and tardiness penalty are generated from the uniform distribution [1,10]. Let P be the sum of processing times of all the jobs. For each job, an integer due date is generated from the uniform distribution [P(1 - T - R/2), P(1 - T + R/2)], where T is the tardy factor, set at 0.0, 0.2, 0.4, 0.6, 0.8 and 1.0, and R is the range factor, set at 0.2, 0.4, 0.6 and 0.8. For each combination of parameters, two problems are generated.
The problems are solved using several heuristic search algorithms such as:
The lower bound computation method proposed in Reference-1 is used for computing the under-estimating heuristic over the unscheduled jobs, for solving using the heuristic search methods.
If you are using these benchmarks for your paper, please let us know (vsgautam.iitkgp@gmail.com). Also, please let us know if you are able to find better solutions to the given benchmarks along with the details of your method.
Reference-1: George Li, Single machine earliness and tardiness scheduling, European Journal of Operational Research (EJOR), Elsevier, vol.96, no.3, pp.546–558, Feb. 1997.
The following papers are known to use these benchmarks:
S. G. Vadlamudi, Sandip Aine, P. P. Chakrabarti, Anytime Pack Search, Natural Computing, Special Issue: Pattern Recognition and Mining, Springer, vol.15, no.3, pp.395-414, Sep. 2016. Includes Parallel Anytime Pack Search.
S. G. Vadlamudi, Sandip Aine, P. P. Chakrabarti, Anytime Pack Heuristic Search, 5th International Conference on Pattern Recognition and Machine Intelligence (PReMI), Springer, LNCS, vol.8251 (Pattern Recognition and Machine Intelligence), pp.628-634, 10-14 Dec. 2013, Kolkata, India.
S. G. Vadlamudi, Sandip Aine, P. P. Chakrabarti, Incremental Beam Search, Information Processing Letters (IPL), Elsevier, vol.113, no.22-24, pp.888-893, Nov.-Dec. 2013.