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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016064
Classification : 49-XX
Mots clés : Robotic cell, flow shop, controllable processing times, MIP-base heuristic, genetic algorithm
Al-Salem, Mohammed 1 ; Kharbeche, Mohamed 2

1 Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar.
2 Qatar Transportation and Traffic Safety Center, Qatar University, Doha, Qatar.
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2016064/

M.S. Akturk and T. Ilhan, Single cnc machine scheduling with controllable processing times to minimize total weighted tardiness. Comput. Oper. Res. 38 (2011) 771–781. | DOI | MR | Zbl

N. Al-Dhaheri and A. Diabat, The quay crane scheduling problem. J. Manufact. Syst. 36 (2015) 87–94. | DOI

N. Al-Dhaheri, A. Jebali and A. Diabat, 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

D. Biskup and T.E. Cheng, Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Engrg. Optim. 31 (1999) 329–336. | DOI

J. Carlier, M. Haouari, M. Kharbeche and A. Moukrim, 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

A. Diabat, 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

A. Diabat and E. Theodorou, An integrated quay crane assignment and scheduling problem. Comput. Indus. Eng. 73 (2014) 115–123. | DOI

A. Diabat and M. Al-Salem, An integrated supply chain problem with environmental considerations. Int. J. Prod. Econ. 164 (2015) 330–338. | DOI

A. Diabat and R. Deskoores, A hybrid genetic algorithm based heuristic for an integrated supply chain problem. J. Manufact. Syst. 38 (2016) 172–180. | DOI

A. Diabat, O. Battaïa and D. Nazzal, An improved lagrangian relaxation-based heuristic for a joint location-inventory problem. Comput. Oper. Res. 61 (2015) 170–178. | DOI | MR | Zbl

H. Gultekin, M.S. Akturk and O.E. Karasan, Bicriteria robotic cell scheduling. J. Schedul. 11 (2008) 457–473. | DOI | MR | Zbl

H. Gultekin, M.S. Akturk and O.E. Karasan, Bicriteria robotic operation allocation in a flexible manufacturing cell. Comput. Oper. Res. 37 (2010) 779–789. | DOI | Zbl

N.G. Hall and C. Sriskandarajah, A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44 (1996) 510–525. | DOI | MR | Zbl

Y.-M. Fu, A. Diabat and I.-T. Tsai, A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach. Expert Syst. Appl. 41 (2014) 6959–6965. | DOI

A. Janiak, Single machine scheduling problem with a common deadline and resource dependent release dates. Eur. J. Oper. Res. 53 (1991) 317–325. | DOI | Zbl

S.M. Johnson, Optimal two-and three-stage production schedules with setup times included. Nav. Res. Logist. Q. 1 (1954) 61–68. | DOI | Zbl

M. Karimi-Nasab and S.F. Ghomi, Multi-objective production scheduling with controllable processing times and sequence-dependent setups for deteriorating items. Int. J. Prod. Res. 50 (2012) 7378–7400. | DOI

V. Kayvanfar, G.M. Komaki, A. Aalaei and M. Zandieh, Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times. Comput. Oper. Res. 41 (2014) 31–43. | DOI | MR | Zbl

M. Kharbeche, J. Carlier, M. Haouari and A. Moukrim, Exact methods for the robotic cell problem. Flexible Ser. Manufact. J. 23 (2011) 242–261. | DOI | Zbl

C. Koulamas, S. Gupta and G.J. Kyparisis, 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

K. Li, Y. Shi, S.-L. Yang and B.-Y. Cheng, Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. App. Soft Comput. 11 (2011) 5551–5557. | DOI

B. Mor and G. Mosheiov, Batch scheduling of identical jobs with controllable processing times. Comput. Oper. Res. 41 (2014) 115–124. | DOI | MR | Zbl

M. Nawaz, E.E. Enscore and I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11 (1983) 91–95. | DOI

G. Niu, S. Sun, P. Lafon, Y. Zhang and J. Wang, Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times. Int. J. Prod. Res. 50 (2012) 7415–7427. | DOI

Y.-B. Park, Optimizing robot’s service movement in a robot-centered fmc. Comput. Indus. Eng. 27 (1994) 47–50. | DOI

P. Renna, Controllable processing time policies for job shop manufacturing system. Int. J. Adv. Manufact. Technol. 67 (2013) 2127–2136. | DOI

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times. Disc. Appl. Math. 155 (2007) 1643–1666. | DOI | MR | Zbl

D. Shabtay, M. Kaspi and G. Steiner, The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times. IIE Trans. 39 (2007) 539–557. | DOI

H.D. Sherali and W.P. Adams, 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

A. Shioura, N.V. Shakhlevich and V.A. Strusevich, 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

Z. Uruk, H. Gultekin and M.S. Akturk, Two-machine flowshop scheduling with flexible operations and controllable processing times. Comput. Oper. Res. 40 (2013) 639–653. | DOI | MR | Zbl

D. Vasiljevic and M. Danilovic, Handling ties in heuristics for the permutation flow shop scheduling problem. J. Manufact. Syst. 35 (2015) 1–9. | DOI

K. Xu, Z. Feng and K. Jun, 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

K. Xu, Z. Feng and L. Ke, 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

K. Xu, Z. Feng and L. Ke, Single machine scheduling with total tardiness criterion and convex controllable processing times. Ann. Oper. Res. 186 (2011) 383–391. | DOI | MR | Zbl

D.-L. Yang, T. Cheng and S.-J. Yang, 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

N. Yin and X.-Y. Wang, Single-machine scheduling with controllable processing times and learning effect. Int. J. Adv. Manufact. Technol. 54 (2011) 743–748. | DOI

Y. Yin, T. Cheng, C.-C. Wu and S.-R. Cheng, Single-machine common due-date scheduling with batch delivery costs and resource-dependent processing times. Int. J. Prod. Res. 51 (2013a) 5083–5099. | DOI

Y. Yin, T.E. Cheng, C.-C. Wu, S.-R. Cheng, 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

S. Yildiz, M.S. Akturk and O.E. Karasan, Bicriteria robotic cell scheduling with controllable processing times. Int. J. Prod. Res. 49 (2011) 569–583. | DOI | Zbl

S. Zdrzałka, 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

Q. Zeng, A. Diabat and Q. Zhang, A simulation optimization approach for solving the dual-cycling problem in container terminals. Maritime Policy Manage. 42 (2015) 806–826. | DOI

Cité par Sources :