The present paper considers the problem of scheduling a set of jobs where some jobs may be rejected. The objective function consists of minimizing two criteria simultaneously: the sum of the weighted completion times of the accepted jobs and the sum of the rejection costs. Although the characteristics of this problem have been discussed in the literature, no solution algorithm has yet been proposed. Herein, solution algorithms are developed using two meta-heuristic methods: Pareto simulated annealing (PSA), a multiple-objective optimization approach; and colonial competitive algorithm (CCA), a novel method which is adopted for the first time in a discrete multiple-objective optimization problem. Computational testing illustrates the practicality of both algorithms to find a good estimation of the Pareto optimal set. The quality of the proposed algorithms are evaluated and compared by some available performance measures and a new measure introduced in the paper. The comparative results show that CCA offers better estimation of the Pareto optimal set than PSA.
ChengY.SunS., Scheduling linear deteriorating jobs with rejection on a single machine. Eur. J. Oper. Res.194 (1) (2009): 18–27. DOI: 10.1016/j.ejor.2007.11.047.
2.
EngelsD. W.KargerD. R.KolliopoulosS. G.SenguptaS.UmaR. N.WeinJ., Techniques for scheduling with rejection. J. Algorithms49 (1) (2003): 175–191.
3.
Nagy-GyorgyJ.ImrehC., Online scheduling with machine cost and rejection. Discrete Appl. Math.155 (18) (2007): 2546–2554.
4.
GrahamR. L.LawlerE. L.LenstraJ. K.Rinnooy KanA. H. G., Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math., 5 (1979): 287–326.
5.
SmithW. E., Various optimizers for single stage production. Nav. Res. Logist.3 (1) (1956): 59–66.
6.
BartalY.LeonardiS.Marchetti-SpaccamelaA.SgallJ.StougieL., Multiprocessor scheduling with rejection. SIAM J. Discrete Math.13 (1) (2000): 64–78.
7.
PruhsK.SgallJ.TorngE., In Handbook of scheduling: Algorithms, models, and performance analysis (Ed. LeungJ. Y. T.), 2004, pp. 15-1–15-41 (CRC Press, Florida, USA).
8.
EpsteinL.NogaJ.WoegingerG. J., Online scheduling of unit time jobs with rejection: Minimization the total completion time. Oper. Res. Lett.30 (6) (2002): 415–420.
BansalN.BlumA.ChawlaS.DhamdhereK., Scheduling for flow time with admission control. Lect. Notes Comput. Sci., 2832 (2003): 43–54.
14.
BundeD. P., Scheduling on a single machine to minimize total flow time with job rejections. In Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory & Applications, Stern School of Business, New York, 18–21 July 2005, pp. 562–572.
15.
DosaG.HeY., Preemptive and non-preemptive online algorithms for scheduling with rejection of two uniform machines. Computing76 (1) (2006): 149–164.
16.
DosaG.HeY., Scheduling with machine cost and rejection. J. Combin. Optim.12 (4) (2006): 337–350.
EgleseR. W., Simulated annealing: A tool for operational research. Eur. J. Oper. Res.46 (3) (1990): 271–281.
23.
FleischerM. A., Simulated annealing: Past, present, and future’. In Proceedings of the 1995 Winter Simulation Conference, Arlington, Virginia, USA, 3–6 December 1995, pp. 155–161 (IEEE Computer Society Washington, DC, USA).
24.
KoulamasC.AntonyS. R.JaenR., A survey of simulated annealing applications to operations research problems. Int. J. Mgmt Sci.22 (1) (1994): 41–56.
25.
RomeoF.Sangiovanni-VincentelliA., A theoretical framework for simulated annealing. Algorithmica6 (3) (1991): 302–345.
26.
SumanB., Study of simulated annealing based algorithms for multi-objective optimization of a constrained problem. Comput. Chem. Engng28 (9) (2004): 1849–1871.
27.
MansouriS. A., A simulated annealing approach to a bi-criteria sequencing problem in a two-stage supply chain. Comput. Ind. Engng50 (1) (2006): 105–119.
28.
Atashpaz-GargariE.LucasC., Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition’. In Proceedings of the IEEE Congress on Evolutionary Computation, Singapore, 2007, pp. 4661–4667.
29.
Atashpaz-GargariE.HashemzadehF.RajabiounR.LucasC., Colonial competitive algorithm, a novel approach for PID controller design in MIMO distillation column process. Int. J. Intell. Comput. Cybernet.1 (3) (2008): 337–355.
30.
RajabiounR.Atashpaz-GargariE.LucasC., Colonial competitive algorithm as a tool for Nash equilibrium point achievement. Lect. Notes Comput. Sci., 5073 (2008): 680–695.
31.
Atashpaz-GargariE.HashemzadehF.LucasC., Designing MIMO PID controller using colonial competitive algorithm: Applied to distillation column process’. In Proceedings of IEEE CEC, within IEEE WCCI, Hong Kong, 2008, pp. 1929–1934.
32.
KhabbaziA.Atashpaz-GargariE.LucasC., Imperialist competitive algorithm for minimum bit error rate beam forming. Int. J. Bio-Inspired Comput.1 (1/2) (2009): 125–133.
33.
RajabiounR.HashemzadehF.Atashpaz-GargariE.MesgariB.Rajaei SalmasiF., Identification of a MIMO evaporator and its decentralized PID controller tuning using colonial competitive algorithm. In Proceedings of the 17th International Federation of Automatic Control World Congress, Seoul, South Korea, 6–11 July 2008, pp. 9952–9957 (Elsevier IFAC Publication).
