×

Minimizing the makespan on two identical parallel machines with mold constraints. (English) Zbl 1458.90277

Summary: This paper deals with the scheduling problem of minimizing the makespan on two identical parallel machines with molds as resource constraints. Two or more jobs with the same mold requirement cannot be processed on the same or different machines at the same time. While quite common in practice, like in wafer fabrication, such problems have not received much attention in the literature. Since this problem is NP-hard, a mathematical model for solving it is derived and tested. Moreover, three simple, fast, and effective heuristics are proposed with a worst-case performance ratio of 3/2. Computational results show that the proposed heuristics can efficiently obtain good solutions for problem instances containing a large number of jobs. In addition, the use of these proposed algorithms as initial solution can improve the performance of metaheuristics. Furthermore, the solutions obtained by these proposed heuristics can be improved by metaheuristics.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blazewicz, J.; Dror, M.; Weglarz, J., Mathematical programming formulations for machine scheduling: asurvey, Eur. J. Oper. Res., 51, 283-300 (1991) · Zbl 0734.90040
[2] Blazewicz, J.; Kubiak, W.; Röck, H.; Szwarcfiter, J., Minimizing mean flow-time with parallel processors and resource constraints, Acta Inf., 25, 5, 513-524 (1987) · Zbl 0606.68030
[3] Beezão, A. C.; Cordeau, J.-F.; Laporte, G.; Yanasse, H. H., Scheduling identical parallel machines with tooling constraints, Eur. J. Oper. Res., 257, 834-844 (2017) · Zbl 1394.90263
[4] Boco, D., An algorithm to generate random numbers with binomial distribution, Yugoslav J. Oper. Res., 10, 99-108 (2000)
[5] Brucker, P.; Dhaenens-Flipo, C.; Knust, S.; Kravchenko, S. A.; Werner, F., Complexity results for parallel-machine scheduling with a single server, J. Scheduling, 5, 429-457 (2002) · Zbl 1040.90016
[6] Coffman, E. G.; Garey, M. R.; Johnson, D. S., An application of bin packing to multi-processor scheduling, SIAM J. Comput., 7, 1-17 (1978) · Zbl 0374.68032
[7] Daniels, R. L.; Hoopes, B. J.; Mazzola, J. B., Scheduling parallel manufacturing cells with resource flexibility, Manage. Sci., 42, 1260-1276 (1996) · Zbl 0880.90060
[8] Daniels, R. L.; Hua, S. Y.; Webster, S., Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment, Comput. Oper. Res., 26, 143-155 (1999) · Zbl 0947.90045
[9] Davidovic, T.; Selmic, M.; Teodorovic, D.; Ramljak, D., Bee colony optimization for scheduling independent tasks to identical processors, J. Heuristics, 18, 549-569 (2012) · Zbl 1358.90004
[10] Dell’Amico, M.; Iori, M.; Martello, S.; Monaci, M., Heuristic and exact algorithms for the identical parallel-machine scheduling problem, J. Heuristics, 20, 333-344 (2008) · Zbl 1243.90060
[11] Dell’Amico, M.; Martello, S., Optimal scheduling of tasks on identical parallel processors, INFORMS J. Comput., 7, 191-200 (1995) · Zbl 0859.90081
[12] Edis, E. B.; Oguz, C.; Ozkarahan, I., Machine scheduling with additional resources: notation, classification, models and solution methods, Eur. J. Oper. Res., 230, 449-463 (2013) · Zbl 1317.90116
[13] Fathi, Y.; Barnette, K. W., Heuristic procedures for the parallel machine problem with tool switches, Int. J. Prod. Res., 40, 151-164 (2002) · Zbl 1175.90163
[14] Friesen, D. K., Tighter bounds for the multifit processor scheduling algorithm, SIAM J. Comput., 13, 170-181 (1984) · Zbl 0539.68024
[15] Garey, M. R.; Graham, R. L., Bounds for multiprocessor scheduling with resource constraints, SIAM J. Comput., 4, 187-200 (1975) · Zbl 0333.68041
[16] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W. H. Freeman · Zbl 0411.68039
[17] Graham, R. L., Bounds for certain multiprocessing anomalies, Bell Labs Tech. J., 45, 1563-1581 (1966) · Zbl 0168.40703
[18] Gupta, J. N.D.; Ruiz-Torres, A. J., A LISTFIT heuristic for minimizing makespan on identical parallel machines, Prod. Plann. Control, 12, 28-36 (2001)
[19] Ham, A. M.; Cho, M., A practical two-phase approach to scheduling of photolithography production, IEEE Trans. Semicond. Manuf., 28, 367-373 (2015)
[20] Hansen, P.; Mladenović, N., Variable neighborhood search, Comput. Oper. Res., 191, 593-595 (2008)
[21] Hasani, K.; Kravchenko, S.; Werner, F., Simulated annealing and genetic algorithms for the two-machine scheduling problem with a single server, Int. J. Prod. Res., 52, 13, 3778-3792 (2014)
[22] Hasani, K.; Kravchenko, S.; Werner, F., Minimizing the makespan for the two-machine scheduling problem with a single server: two algorithms for very large instances, Eng. Optim., 48, 1, 173-183 (2016)
[23] Hong, T.-P.; Sun, P.-C.; Li, S.-D., A heuristic algorithm for scheduling problem of parallel machines with mold constraints, WSEAS Trans. Syst., 7, 6, 642-651 (2008)
[24] Lee, C. L.; Massey, D., Multiprocessor scheduling: combining LPT and MULTIFIT, Discrete Appl. Math., 20, 233-242 (1988) · Zbl 0655.90036
[25] Lee, W. C.; Wu, C. C.; Chen, P., A simulated annealing approach to makespan minimization on identical parallel machines, Int. J. Adv. Manuf.Technol., 31, 328-334 (2006)
[26] Liao, C. J.; Tjandradjaja, E.; Chung, T. P., An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem, Appl. Soft Comput., 12, 1755-1764 (2012)
[27] Lodi, A.; Tramontani, A., Performance variability in mixed-integer programming, Tutorials Oper. Res., 1-12 (2013)
[28] Min, L.; Cheng, W., A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines, Artif. Intell. Eng., 13, 399-403 (1999)
[29] Mokotoff, E., An exact algorithm for the identical parallel-machine scheduling problem, Eur. J. Oper. Res., 152, 758-769 (2004) · Zbl 1043.90030
[30] Niemeier, M.; Wiese, A., Scheduling with an orthogonal resource constraint, Algorithmica, 71, 837-858 (2015) · Zbl 1325.68038
[31] Paiva, G. S.; Carvalho, M. A.M., Improved heuristic algorithms for the job sequencing and tool switching problem, Comput. Oper. Res., 88, 208-219 (2017) · Zbl 1391.90228
[32] Reklaitis, G. V., Overview of Scheduling and Planning of Batch Process Operations (1996), Springer: Springer Berlin Heidelberg
[33] Sethi, R., On the complexity of mean flow time scheduling, Math. Oper. Res., 2, 320-330 (1977) · Zbl 0402.90046
[34] Tian, Y.; Liu, D.; Yuan, D.; Wang, K., A discrete PSO for two-stage assembly scheduling problem, Int. J. Adv. Manuf.Technol., 66, 481-499 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.