In this paper, we present a MIP-based heuristic and an effective genetic algorithm for the Robotic Cell Problem with Controllable Processing Times (RCPCPT). This problem arises in modern automated manufacturing systems and requires simultaneously scheduling jobs, machines, and transportation devices in order to maximize the throughput or minimize the makespan. The RCPCPT is modeled as a flow shop problem with blocking constraints, a single transport robot, and controllable processing times. This latter feature of the model refers to the fact that the processing times are not fixed but vary linearly with the acceleration cost and therefore should be determined as part of the problem output. We formulate the problem as a nonlinear mixed-integer programming formulation and we use its linearized form to derive LP- and MIP-based heuristics. In addition, we proposed a genetic algorithm consistently yields near-optimal solution and it encompasses several novel features including, an original solution encoding as well as a mutation operator that requires iteratively solving MIPs in order to generate feasible processing times. Finally, we present a computational study for the proposed formulation, heuristics and genetic algorithm and we provide an empirical evidence of the effectiveness of the MIP-based heuristic for small instances and the genetic algorithm for large instances.
Accepté le :
DOI : 10.1051/ro/2016064
Mots clés : Robotic cell, flow shop, controllable processing times, MIP-base heuristic, genetic algorithm
@article{RO_2017__51_3_805_0,
author = {Al-Salem, Mohammed and Kharbeche, Mohamed},
title = {Throughput optimization for the {Robotic} {Cell} {Problem} with {Controllable} {Processing} {Times}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {805--818},
publisher = {EDP-Sciences},
volume = {51},
number = {3},
year = {2017},
doi = {10.1051/ro/2016064},
mrnumber = {3880526},
zbl = {1398.90106},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2016064/}
}
TY - JOUR AU - Al-Salem, Mohammed AU - Kharbeche, Mohamed TI - Throughput optimization for the Robotic Cell Problem with Controllable Processing Times JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 805 EP - 818 VL - 51 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2016064/ DO - 10.1051/ro/2016064 LA - en ID - RO_2017__51_3_805_0 ER -
%0 Journal Article %A Al-Salem, Mohammed %A Kharbeche, Mohamed %T Throughput optimization for the Robotic Cell Problem with Controllable Processing Times %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 805-818 %V 51 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2016064/ %R 10.1051/ro/2016064 %G en %F RO_2017__51_3_805_0
Al-Salem, Mohammed; Kharbeche, Mohamed. Throughput optimization for the Robotic Cell Problem with Controllable Processing Times. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 805-818. doi : 10.1051/ro/2016064. http://archive.numdam.org/articles/10.1051/ro/2016064/
and , Single cnc machine scheduling with controllable processing times to minimize total weighted tardiness. Comput. Oper. Res. 38 (2011) 771–781. | DOI | MR | Zbl
and , The quay crane scheduling problem. J. Manufact. Syst. 36 (2015) 87–94. | DOI
, and , A simulation-based genetic algorithm approach for the quay crane scheduling under uncertainty. Simul. Model. Pract. Theory 66 (2016) 122–138. | DOI
M. Al-Salem, M. Haouari, M. Kharbeche and W. Khallouli, A free-slack-based genetic algorithm for the robotic cell problem with controllable processing times, in: Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling. Springer (2016) 77–93. | MR
and , Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Engrg. Optim. 31 (1999) 329–336. | DOI
, , and , An optimization-based heuristic for the robotic cell problem. Eur. J. Oper. Res. 202 (2010) 636–645. | DOI | Zbl
M.W. Dawande, H.N. Geismar, S.P. Sethi and C. Sriskandarajah. Vol. 101 of Throughput optimization in robotic cells. Springer Science & Business Media (2007). | Zbl
, Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain. Eur. J. Oper. Res. 238 (2014) 114–121. | DOI | MR | Zbl
and , An integrated quay crane assignment and scheduling problem. Comput. Indus. Eng. 73 (2014) 115–123. | DOI
and , An integrated supply chain problem with environmental considerations. Int. J. Prod. Econ. 164 (2015) 330–338. | DOI
and , A hybrid genetic algorithm based heuristic for an integrated supply chain problem. J. Manufact. Syst. 38 (2016) 172–180. | DOI
, and , An improved lagrangian relaxation-based heuristic for a joint location-inventory problem. Comput. Oper. Res. 61 (2015) 170–178. | DOI | MR | Zbl
, and , Bicriteria robotic cell scheduling. J. Schedul. 11 (2008) 457–473. | DOI | MR | Zbl
, and , Bicriteria robotic operation allocation in a flexible manufacturing cell. Comput. Oper. Res. 37 (2010) 779–789. | DOI | Zbl
and , A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44 (1996) 510–525. | DOI | MR | Zbl
, and , A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach. Expert Syst. Appl. 41 (2014) 6959–6965. | DOI
, Single machine scheduling problem with a common deadline and resource dependent release dates. Eur. J. Oper. Res. 53 (1991) 317–325. | DOI | Zbl
, Optimal two-and three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1 (1954) 61–68. | DOI | Zbl
and , Multi-objective production scheduling with controllable processing times and sequence-dependent setups for deteriorating items. Int. J. Prod. Res. 50 (2012) 7378–7400. | DOI
, , and , Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times. Comput. Oper. Res. 41 (2014) 31–43. | DOI | MR | Zbl
, , and , Exact methods for the robotic cell problem. Flexible Ser. Manufact. J. 23 (2011) 242–261. | DOI | Zbl
, and , A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times. Eur. J. Oper. Res. 205 (2010) 479–482. | DOI | Zbl
, , and , Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. App. Soft Comput. 11 (2011) 5551–5557. | DOI
and , Batch scheduling of identical jobs with controllable processing times. Comput. Oper. Res. 41 (2014) 115–124. | DOI | MR | Zbl
, and , A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11 (1983) 91–95. | DOI
, , , and , Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times. Int. J. Prod. Res. 50 (2012) 7415–7427. | DOI
, Optimizing robot’s service movement in a robot-centered fmc. Comput. Indus. Eng. 27 (1994) 47–50. | DOI
, Controllable processing time policies for job shop manufacturing system. Int. J. Adv. Manufact. Technol. 67 (2013) 2127–2136. | DOI
and , A survey of scheduling with controllable processing times. Disc. Appl. Math. 155 (2007) 1643–1666. | DOI | MR | Zbl
, and , The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times. IIE Trans. 39 (2007) 539–557. | DOI
and , A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3 (1990) 411–430. | DOI | MR | Zbl
, and , A submodular optimization approach to bicriteria scheduling problems with controllable processing times on parallel machines. SIAM J. Discrete Math. 27 (2013) 186–204. | DOI | MR | Zbl
, and , Two-machine flowshop scheduling with flexible operations and controllable processing times. Comput. Oper. Res. 40 (2013) 639–653. | DOI | MR | Zbl
and , Handling ties in heuristics for the permutation flow shop scheduling problem. J. Manufact. Syst. 35 (2015) 1–9. | DOI
, and , A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates. Comput. Oper. Res. 37 (2010) 1924–1938. | DOI | MR | Zbl
, and , A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates. Ann. Oper. Res. 181 (2010) 303–324. | DOI | MR | Zbl
, and , Single machine scheduling with total tardiness criterion and convex controllable processing times. Ann. Oper. Res. 186 (2011) 383–391. | DOI | MR | Zbl
, and , Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions. Int. J. Prod. Res. 52 (2014) 1133–1141. | DOI
and , Single-machine scheduling with controllable processing times and learning effect. Int. J. Adv. Manufact. Technol. 54 (2011) 743–748. | DOI
, , and , Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times. Int. J. Prod. Res. 51 (2013a) 5083–5099. | DOI
, , , , Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time. J. Oper. Res. Soc. 65 (2013b) 1–13. | DOI
, and , Bicriteria robotic cell scheduling with controllable processing times. Int. J. Prod. Res. 49 (2011) 569–583. | DOI | Zbl
, Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis. Oper. Res. Lett. 10 (1991) 519–523. | DOI | MR | Zbl
, and , A simulation optimization approach for solving the dual-cycling problem in container terminals. Maritime Policy Manage. 42 (2015) 806–826. | DOI
Cité par Sources :
